Description
You are given a rows x cols matrix grid representing a field of cherries. Two robots start at row 0 and try to collect maximum cherries moving down. They can only move down, down-left, or down-right. Return the maximum cherries collected.
Examples
Input:
grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]Output:
24Explanation:
Optimal paths collect 24 cherries.
Input:
grid = [[1]]Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
grid = [[1,0,0,3],[0,0,0,0],[0,0,1,0],[2,0,0,2]]Output:
8Explanation:
Robot 1 starts at (0,0) and follows path (0,0)->(1,1)->(2,2)->(3,3) collecting 1+0+1+2=4 cherries. Robot 2 starts at (0,3) and follows path (0,3)->(1,2)->(2,1)->(3,0) collecting 3+0+0+2=5 cherries. Combined total: 9 cherries.
Constraints
- •
rows == grid.length - •
cols == grid[i].length - •
2 ≤ rows, cols ≤ 70