Cherry Pickup II
You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries at cell (i, j).
Two robots start at (0, 0) and (0, cols - 1) respectively. Each robot can move from (r, c) to (r+1, c-1), (r+1, c), or (r+1, c+1). Both robots move simultaneously until they reach the last row.
Return the maximum number of cherries collected by both robots. If both robots are on the same cell, only one cherry is collected.
Examples
Input: [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Input: [[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,1],[0,1,0,0,0]]
Output: 4
Hints
Consider modeling the problem as a dynamic programming (DP) problem where the state represents the positions of both robots at each step. Think about how to represent the state and what transitions are possible.
To avoid double-counting cherries when both robots are on the same cell, introduce a condition in your DP state or transition to ensure that overlapping cells are only counted once.
Optimize the DP solution by using memoization or tabulation to store intermediate results, and recognize that the state can be represented by the column positions of both robots at each row, reducing the problem to a 2D DP problem.
Cherry Pickup II
You are given a `rows x cols` matrix `grid` representing a field of cherries where `grid[i][j]` represents the number of cherries at cell `(i, j)`.