You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.
You have two robots that can collect cherries for you:
(0, 0), and(0, cols - 1).Return the maximum number of cherries collection using both robots by following the rules below:
(i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).grid.Example 1:
Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]] Output: 24 Explanation: 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 Explanation: 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.lengthcols == grid[i].length2 <= rows, cols <= 700 <= grid[i][j] <= 100Cherry Pickup II is a classic dynamic programming on grids problem where two robots start at the top row and move downward to collect the maximum number of cherries. Each robot can move diagonally left, straight down, or diagonally right at every step. The challenge is that both robots move simultaneously and may land on the same cell.
A common strategy is to define a 3D DP state such as dp[row][col1][col2], representing the maximum cherries collected when robot1 is at col1 and robot2 is at col2 in the same row. For each step, consider all possible column transitions for both robots (−1, 0, +1). If both robots land on the same cell, count the cherries only once.
This approach systematically explores all valid states while avoiding recomputation through memoization or bottom‑up tabulation. The overall time complexity is roughly O(rows × cols²), with similar space requirements that can be optimized using rolling arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| 3D Dynamic Programming (row, col1, col2) | O(m × n²) | O(m × n²) or O(n²) with optimization |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming, define DP[i][j][k]: The maximum cherries that both robots can take starting on the ith row, and column j and k of Robot 1 and 2 respectively.
This approach involves using a dynamic programming table to store intermediate results. The state dp[r][c1][c2] represents the maximum cherries we can collect when robot 1 is at position (r, c1) and robot 2 is at (r, c2). The transition involves moving both robots to the next row and trying all possible column moves for each robot.
Time Complexity: O(rows * cols^2)
Space Complexity: O(rows * cols^2)
1def cherryPickup(grid):
2 rows, cols = len(grid), len(grid[0])
3 dp = [[[0] * cols for _ in range(cols)] for _ in range(rows)]
4
5 for r in range(rows - 1, -1, -1):
6 for c1 in range(cols):
7 for c2 in range(cols):
8 for newC1 in [c1, c1 + 1, c1 - 1]:
9 for newC2 in [c2, c2 + 1, c2 - 1]:
10 if 0 <= newC1 < cols and 0 <= newC2 < cols:
11 prev = (dp[r + 1][newC1][newC2] if r + 1 < rows else 0)
12 dp[r][c1][c2] = max(dp[r][c1][c2], prev + grid[r][c1] + (grid[r][c2] if c1 != c2 else 0))
13 return dp[0][0][cols - 1]This function implements a dynamic programming solution. We use a 3D table dp where dp[r][c1][c2] represents the maximum cherries obtainable starting from row r with robot 1 at column c1 and robot 2 at column c2. We transition backwards from the last row to the first row, checking all possible moves for the robots.
This approach uses a recursive function with memoization to calculate the maximum cherries possible. The function recursively tries all valid ways the robots can move to the next row from their current columns, caching results to prevent redundant calculations.
Time Complexity: O(rows * cols^2)
Space Complexity: O(rows * cols^2) for memoization
1public class Solution {
2 public int
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Cherry Pickup II is a well-known hard-level dynamic programming problem often used in advanced coding interview preparation. Variations of multi-agent grid DP problems are commonly discussed in FAANG-style interviews.
A 3D DP state is needed because the positions of both robots affect the number of cherries collected at every step. Tracking row, column1, and column2 ensures that all movement combinations are evaluated correctly.
The optimal approach uses dynamic programming with a 3D state representing the current row and the column positions of both robots. By evaluating all possible moves for both robots at each step, the algorithm maximizes collected cherries while avoiding recomputation through memoization or tabulation.
A multidimensional dynamic programming array or memoization table is the most suitable structure. It efficiently stores intermediate results for each pair of robot positions in a given row.
The Java solution uses recursion with memoization, where dfs is the recursive function that calculates the maximum cherries possible from any given position, storing results in memo to optimize repeat calculations. Each call considers new positions for the robots in the next row.