LeetCode Problem Workspace
Cherry Pickup II
Maximize cherry collection in a grid using two robots with careful state transition dynamic programming to optimize paths efficiently.
3
Topics
5
Code langs
3
Related
Practice Focus
Hard · State transition dynamic programming
Answer-first summary
Maximize cherry collection in a grid using two robots with careful state transition dynamic programming to optimize paths efficiently.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for State transition dynamic programming
This problem requires managing two robots simultaneously, collecting cherries optimally without overlap, using a 3D dynamic programming state. Define DP[i][j][k] as the maximum cherries collected starting at row i with robots at columns j and k. Transition carefully to cover all next moves while avoiding double-counting cherries in the same cell.
Problem Statement
You are given a rows x cols matrix grid representing a field of cherries. Each cell grid[i][j] contains a non-negative number of cherries that can be collected. Two robots start at the first row in different columns and can move only down-left, down, or down-right in each step. Both robots collect cherries from the cells they visit.
Return the maximum number of cherries both robots can collect following these rules. If both robots occupy the same cell in a step, only one robot collects the cherries. Plan the robots' paths from the top row to the bottom row to maximize the total cherries collected.
Examples
Example 1
Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Path of robot #1 and #2 are described in color green and blue respectively. Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12. Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12. Total of cherries: 12 + 12 = 24.
Example 2
Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Path of robot #1 and #2 are described in color green and blue respectively. Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17. Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11. Total of cherries: 17 + 11 = 28.
Constraints
- rows == grid.length
- cols == grid[i].length
- 2 <= rows, cols <= 70
- 0 <= grid[i][j] <= 100
Solution Approach
Define the DP State
Use a 3D DP array DP[i][j][k] representing the maximum cherries collected starting from row i with robot1 at column j and robot2 at column k. This state allows simultaneous tracking of both robots and prevents overlapping cherry counts.
State Transitions
For each DP[i][j][k], iterate through all next possible moves for both robots (down-left, down, down-right). Add cherries collected at positions j and k to the maximum of DP[i+1][next_j][next_k]. Ensure you only count the cherries once if both robots land on the same cell.
Initialization and Iteration
Initialize DP at the bottom row with cherries in their respective positions. Iterate rows upward, computing maximum cherries for each possible pair of robot positions, and finally return DP[0][start_col1][start_col2] as the answer.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(rows * cols^2 * 9) because for each row and pair of robot positions, there are 3x3 next moves. Space complexity is O(rows * cols^2) for the DP array. Optimizations can reduce it to O(cols^2) per row.
What Interviewers Usually Probe
- Checking if you consider both robots simultaneously and handle overlapping cells.
- Watching if DP is defined correctly to avoid recomputation and ensure transitions cover all next moves.
- Observing whether you can reduce space from full 3D to 2D rolling array optimization.
Common Pitfalls or Variants
Common pitfalls
- Counting cherries twice when both robots occupy the same cell.
- Using a 2D DP ignoring the second robot's position, leading to incorrect totals.
- Failing to iterate all 3x3 move combinations for the next row, missing optimal paths.
Follow-up variants
- Single robot cherry pickup with only one path, simpler 2D DP suffices.
- Allow diagonal jumps longer than one cell, requiring extended DP transitions.
- Grid with obstacles where some cells cannot be visited, adding conditional checks in DP.
FAQ
What is the main DP strategy for Cherry Pickup II?
Use a 3D DP array DP[i][j][k] where i is the row, j and k are columns of robot1 and robot2, tracking maximum cherries collected from that state.
Why do we need to check overlapping cells?
If both robots occupy the same cell, counting cherries twice would overestimate the total; the DP must count such cells only once.
Can we reduce space complexity?
Yes, by using a rolling 2D DP for only the current and next row instead of storing the full 3D array for all rows.
How do we handle moves in DP transitions?
Consider all 3x3 combinations of next moves (down-left, down, down-right) for both robots to ensure all paths are explored.
What makes Cherry Pickup II challenging in interviews?
Managing two robots with overlapping positions requires careful state definition and transition logic, testing both DP and edge-case handling skills.
Solution
Solution 1: Dynamic Programming
We define $f[i][j_1][j_2]$ as the maximum number of cherries that can be picked when the two robots are at positions $j_1$ and $j_2$ in the $i$-th row. Initially, $f[0][0][n-1] = grid[0][0] + grid[0][n-1]$, and the other values are $-1$. The answer is $\max_{0 \leq j_1, j_2 < n} f[m-1][j_1][j_2]$.
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
f = [[[-1] * n for _ in range(n)] for _ in range(m)]
f[0][0][n - 1] = grid[0][0] + grid[0][n - 1]
for i in range(1, m):
for j1 in range(n):
for j2 in range(n):
x = grid[i][j1] + (0 if j1 == j2 else grid[i][j2])
for y1 in range(j1 - 1, j1 + 2):
for y2 in range(j2 - 1, j2 + 2):
if 0 <= y1 < n and 0 <= y2 < n and f[i - 1][y1][y2] != -1:
f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x)
return max(f[-1][j1][j2] for j1, j2 in product(range(n), range(n)))Solution 2: Dynamic Programming (Space Optimization)
Notice that the calculation of $f[i][j_1][j_2]$ is only related to $f[i-1][y_1][y_2]$. Therefore, we can use a rolling array to optimize the space complexity. After optimizing the space complexity, the time complexity is $O(n^2)$.
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
f = [[[-1] * n for _ in range(n)] for _ in range(m)]
f[0][0][n - 1] = grid[0][0] + grid[0][n - 1]
for i in range(1, m):
for j1 in range(n):
for j2 in range(n):
x = grid[i][j1] + (0 if j1 == j2 else grid[i][j2])
for y1 in range(j1 - 1, j1 + 2):
for y2 in range(j2 - 1, j2 + 2):
if 0 <= y1 < n and 0 <= y2 < n and f[i - 1][y1][y2] != -1:
f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x)
return max(f[-1][j1][j2] for j1, j2 in product(range(n), range(n)))Continue Topic
array
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
State transition dynamic programming
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Hard
Stay on this level to stabilize interview delivery.
arrow_forward