To solve the problem of finding the maximum number of stones collected (maximum path sum) in a grid while moving only right or down from the top-left to bottom-right corner, we can use dynamic programming (DP). Here's a step-by-step solution:
Approach
The key insight is to use a DP table where dp[i][j] represents the maximum number of stones collected up to cell (i, j). The recurrence relation is:
- For the first row:
dp[0][j] = dp[0][j-1] + grid[0][j](only move right) - For the first column:
dp[i][0] = dp[i-1][0] + grid[i][0](only move down) - For other cells:
dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])(choose the path with more stones: from above or left)
Solution Code
def max_stones_collected(grid):
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
# Initialize DP table
dp = [[0]*cols for _ in range(rows)]
dp[0][0] = grid[0][0]
# Fill first row
for j in range(1, cols):
dp[0][j] = dp[0][j-1] + grid[0][j]
# Fill first column
for i in range(1, rows):
dp[i][0] = dp[i-1][0] + grid[i][0]
# Fill remaining cells
for i in range(1, rows):
for j in range(1, cols):
dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
# Example usage (replace with your grid from the image)
sample_grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(max_stones_collected(sample_grid)) # Output: 29
Explanation
- Initialization: The DP table starts with the top-left cell (since that's the starting point).
- First Row/Column: These are filled by accumulating stones from the left (for rows) or above (for columns) because there's only one way to reach these cells.
- General Cells: For each cell, we take the maximum of the stones from the cell above or the cell to the left, then add the stones in the current cell. This ensures we always take the path with the most stones.
This approach runs in *O(rows cols)** time and space complexity, which is efficient for typical grid sizes. If you provide the exact grid from the image, we can adjust the code to match your input!
Note: If the grid contains obstacles (cells you can't step on), modify the DP table to skip those cells (e.g., set their value to -infinity to avoid choosing them). Let me know if you need that adjustment!


作者声明:本文包含人工智能生成内容。