Project Euler第18题求解遇ArrayOutOfBounds异常求助

Hey there! Let's work through that ArrayOutOfBounds exception you're hitting with Project Euler #18. I’ve messed around with this problem before, so I’ve got a few ideas on what might be tripping you up.

First, Let’s Break Down the Likely Issues #

Your approach of working from the bottom up makes total sense, but the "looking ahead three rows" logic might be introducing index mistakes—even with your min/max checks. Here are the most common culprits:

1. Misaligned Row Indices & Recursion Bounds
   If your 2D array stores the triangle with the bottom row at index n-1 (standard setup), trying to look ahead three rows from near the top (e.g., row 0 or 1) would mean accessing indices like 0+3 = 3 when the array only has 3 rows total. Your min/max checks might not be accounting for how far forward you can safely look based on your current row position.

2. Column Index Overreach
   Remember: each row i has exactly i+1 elements (if storing the triangle top-to-bottom). When checking paths, you can only move to the same column or the next column in the row below. If your code is trying to access columns like j+2 or j-2 when looking ahead, that’s an instant out-of-bounds error.

3. Unclear Recursion Termination
   If your recursive function doesn’t stop when it hits the top row (or bottom row, depending on your traversal direction), it’ll keep trying to access rows that don’t exist, leading to negative indices or indices beyond the array length.

Fixes & Simplifications #

Let’s start with simplifying the logic—you don’t actually need to look ahead three rows to solve this problem! The standard bottom-up approach only requires comparing the current row with the row directly below it. Here’s how to adjust your code:

Step 1: Correct Recursive Logic (Standard Approach)

Instead of jumping three rows, build up the maximum path value by adding each element to the larger of its two adjacent elements in the row below. Here’s a clean recursive implementation with proper index checks:

def max_path_sum(triangle, row, col):
    # Termination condition: we've reached the bottom row
    if row == len(triangle) - 1:
        return triangle[row][col]
    
    # Ensure we don't go out of bounds on columns
    left = max_path_sum(triangle, row + 1, col)
    right = max_path_sum(triangle, row + 1, col + 1)
    
    return triangle[row][col] + max(left, right)

# Example usage (assuming triangle is stored top-to-bottom)
triangle = [
    [3],
    [7, 4],
    [2, 4, 6],
    [8, 5, 9, 3]
]
print(max_path_sum(triangle, 0, 0))  # Should return 23

Step 2: Debug Your Current Code (If You Want to Keep the Three-Row Logic)

If you’re set on your original approach, add debug prints to catch when indices go wrong:

def your_recursive_func(triangle, current_row):
    for j in range(len(triangle[current_row])):
        # Print indices before accessing to spot issues
        print(f"Checking row {current_row}, column {j}")
        print(f"Trying to access rows: {current_row+1}, {current_row+2}, {current_row+3}")
        
        # Add guards for row existence first
        if current_row + 1 >= len(triangle):
            continue  # No rows below, skip
        if current_row + 2 >= len(triangle):
            # Only process up to current_row+1
            pass
        if current_row + 3 >= len(triangle):
            # Only process up to current_row+2
            pass
        
        # Rest of your logic here...

This will show you exactly when you’re trying to access a row or column that doesn’t exist, so you can adjust your bounds checks accordingly.

Step 3: Verify Array Structure

Double-check how you’re storing the triangle. If you reversed it (bottom row at index 0), your row indices will work in the opposite direction—so looking "forward" would mean decreasing the index, not increasing it. Mixing this up is a super easy mistake to make!

Final Tips #

• Iterative is Often Safer: For this problem, an iterative bottom-up approach avoids recursion-related index headaches entirely. Here’s a quick example:

  def max_path_iterative(triangle):
      # Start from the second-to-last row and work up
      for i in range(len(triangle)-2, -1, -1):
          for j in range(len(triangle[i])):
              # Add the max of the two adjacent elements below
              triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
      return triangle[0][0]
  

• Always Guard Indices: Before accessing triangle[i][j], confirm 0 <= i < len(triangle) and 0 <= j < len(triangle[i])—even if you think your logic should prevent invalid indices.

内容的提问来源于stack exchange，提问作者GBlodgett