Skip to main content

1463. Cherry Pickup II

hard

Two robots start at the top corners of a grid, walk to the bottom row collecting cherries with three downward moves each. Same multi-agent DP idea as Cherry Pickup, but the two walkers are already in lockstep by row.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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: Robot #1 is located at the top-left corner (0, 0), and Robot #2 is located at the top-right corner (0, cols - 1). Return the maximum number of cherries collection using both robots by following the rules below: From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1). When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell. When both robots stay in the same cell, only one takes the cherries. Both robots cannot move outside of the grid at any moment. Both robots should reach the bottom row in grid.

Constraints

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Both robots advance one row per step, so their row index is always the current iteration — only the two column positions vary.

Hint 2

dp[row][c1][c2] = max cherries collectible from row..rows-1 given robot 1 at column c1 and robot 2 at column c2.

Hint 3

Transition: try all 9 combinations of next columns ({c1-1, c1, c1+1} x {c2-1, c2, c2+1}); ignore moves that leave the grid.

Hint 4

When c1 == c2 add the cell value once, not twice.

Solution approach

Reveal approach

Top-down memoization on (row, c1, c2) is the typical implementation. Base case: when row == rows - 1, return grid[row][c1] + (c1 == c2 ? 0 : grid[row][c2]) — count the bottom row's cherries (once if both robots land on it). Recurrence: for the current row add grid[row][c1] + grid[row][c2] minus the duplicate if c1 == c2, then try all 9 combinations of next columns from c1 - 1, c1, c1 + 1 and c2 - 1, c2, c2 + 1, ignoring out-of-bounds. Return the cell contribution plus the max of the 9 recursive results. Start at (0, 0, cols - 1). Bottom-up version sweeps rows from rows-1 down to 0 with a 2D dp[c1][c2] table.

Complexity

Time
O(rows * cols^2)
Space
O(rows * cols^2)

Related patterns

  • dynamic-programming
  • grid-dp
  • multi-agent-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Cherry Pickup II and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →