Cherry Pickup II: Two Robots Collecting Maximum Cherries
You are given a rows x cols grid where each cell contains a number of cherries. Two robots start at the top row: Robot 1 at column 0 and Robot 2 at column cols - 1. On each step, both robots move down one row and can shift one column left, stay in the same column, or shift one column right. They collect cherries from whatever cell they land on, but if both land on the same cell, the cherries are counted only once. Return the maximum total cherries both robots can collect by the time they reach the bottom row.
This is LeetCode 1463: Cherry Pickup II.
Why this problem matters
This problem is a masterclass in multi-dimensional dynamic programming. It forces you to track two agents moving simultaneously through the same grid, which introduces a dimension most DP problems do not have. You cannot greedily pick the best path for one robot and then the best remaining path for the other, because their choices interact. Each robot's position affects what the other can optimally collect.
The "two entities moving in sync" pattern shows up in several contexts beyond cherry grids. Anytime you need to coordinate two pointers, two agents, or two selections that proceed through a shared structure in lockstep, the same DP framework applies. The key lesson is that you model the combined state of both entities, not each one independently.
Once you internalize this pattern, problems like "Cherry Pickup I" (LeetCode 741), multi-path grid traversals, and other coordination problems become much more approachable. The technique also reinforces a broader DP skill: recognizing when your state needs extra dimensions because multiple decisions happen at each step.
The key insight
Both robots move down one row at a time, so after processing row i, both are somewhere in row i. Their combined state at any row is just the pair (c1, c2) representing Robot 1's column and Robot 2's column. Since each robot can move to three possible columns on the next row (left, same, right), there are 3 x 3 = 9 transitions from any state (c1, c2) in row i to states in row i + 1.
You can define dp[c1][c2] as the maximum cherries both robots can collect from the current row onward, given that Robot 1 is in column c1 and Robot 2 is in column c2. Process the grid from the bottom row upward. At each row, for each pair (c1, c2), add the cherries at those positions (counting once if c1 == c2) and take the maximum over all 9 transitions to the next row's DP table. Since you only need the DP values from the row below, you can use a rolling 2D array instead of a full 3D table.
The solution
def cherry_pickup(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(cols)]
for c1 in range(cols):
for c2 in range(cols):
if c1 == c2:
dp[c1][c2] = grid[rows - 1][c1]
else:
dp[c1][c2] = grid[rows - 1][c1] + grid[rows - 1][c2]
for r in range(rows - 2, -1, -1):
new_dp = [[0] * cols for _ in range(cols)]
for c1 in range(cols):
for c2 in range(cols):
best = 0
for dc1 in (-1, 0, 1):
for dc2 in (-1, 0, 1):
nc1, nc2 = c1 + dc1, c2 + dc2
if 0 <= nc1 < cols and 0 <= nc2 < cols:
best = max(best, dp[nc1][nc2])
cherries = grid[r][c1]
if c1 != c2:
cherries += grid[r][c2]
new_dp[c1][c2] = cherries + best
dp = new_dp
return dp[0][cols - 1]
The code starts from the bottom row and fills in the base case: if both robots are in the same column, count those cherries once, otherwise add both. Then it works upward row by row. For each pair of columns (c1, c2) in the current row, it tries all 9 combinations of moves and takes the maximum future value from the DP table of the row below. It adds the current row's cherries to that maximum (being careful not to double-count when c1 == c2) and stores the result.
The final answer is dp[0][cols - 1], because Robot 1 starts at column 0 and Robot 2 starts at column cols - 1 in the top row.
You can also process the grid top-to-bottom instead of bottom-to-top. The logic is the same: define dp[c1][c2] as the maximum cherries collected from row 0 through the current row, and propagate forward. Both directions work, but bottom-up makes the final lookup simpler since the answer is just dp[0][cols - 1] without needing to scan the entire last DP table.
Visual walkthrough
Let's trace through a 4x5 grid to see how the two robots coordinate their movements to maximize total cherry collection.
Robot 1 picks up 3 cherries at (0,0). Robot 2 picks up 0 at (0,4). Running total: 3.
Robot 1 picks up 0 at (1,1). Robot 2 picks up 3 at (1,3). Running total: 3 + 0 + 3 = 6.
Robot 1 picks up 3 at (2,1). Robot 2 picks up 2 at (2,4). Running total: 6 + 3 + 2 = 11.
Robot 1 picks up 4 at (3,2). Robot 2 picks up 2 at (3,3). Final total: 11 + 4 + 2 = 17.
Notice how at each row, both robots choose columns that maximize the combined pickup. Robot 1 tends to cover the left side of the grid while Robot 2 covers the right side, but the DP ensures they cooperate rather than compete. The 9-way branching at each row is what makes brute force exponential, but memoizing on (row, c1, c2) brings it down to polynomial time.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| 3D DP (two robots) | O(m * n^2) | O(n^2) |
Time is O(m * n^2) where m is the number of rows and n is the number of columns. For each of the m rows, you iterate over all n^2 possible column pairs (c1, c2). For each pair, you check 9 transitions, which is constant work. So total time is O(9 * m * n^2), which simplifies to O(m * n^2).
Space is O(n^2). You only keep two 2D arrays of size n x n (the current DP table and the next row's DP table). The full 3D table would be O(m * n^2), but the rolling array optimization reduces it to O(n^2) since each row only depends on the row below.
The building blocks
1. Multi-dimensional state definition
dp = [[0] * cols for _ in range(cols)]
The hardest part of this problem is realizing the DP state needs two column indices, not one. Many grid DP problems use dp[r][c] for a single entity. Here, two entities move simultaneously, so the state becomes dp[c1][c2] for a given row. This "product of positions" pattern generalizes: if you had three agents, you would need three indices. Recognizing when your state needs extra dimensions is one of the most important DP skills.
2. Enumerating paired transitions
for dc1 in (-1, 0, 1):
for dc2 in (-1, 0, 1):
nc1, nc2 = c1 + dc1, c2 + dc2
if 0 <= nc1 < cols and 0 <= nc2 < cols:
best = max(best, dp[nc1][nc2])
Each robot can independently move left, stay, or move right. The nested loop over (-1, 0, 1) for each robot produces all 9 combinations. Bounds checking ensures neither robot steps out of the grid. This "enumerate all move combinations" pattern is reusable whenever two entities make independent choices at each step.
Edge cases
- Single column grid. Both robots start and stay in column 0 for every row. They always overlap, so you just sum each row's single value. The DP handles this naturally since
c1andc2are always 0. - Two columns. The robots start adjacent and can never be more than one column apart. The state space shrinks, but the algorithm works without modification.
- All zeros. Every cell has 0 cherries. The answer is 0. The DP correctly propagates zeros throughout.
- Single row. The robots start at their corners, collect cherries from row 0, and the answer is
grid[0][0] + grid[0][cols - 1](or justgrid[0][0]if there is only one column). No transitions are needed.
From understanding to recall
The conceptual leap in Cherry Pickup II is realizing you need to track both robots' columns as a combined state. Once you see that, the DP is a standard bottom-up fill with a nested transition loop. But under interview pressure, the details matter: initializing the base row correctly, handling the overlap case where c1 == c2, iterating all 9 transitions with bounds checks, and using the rolling array to save space.
Spaced repetition helps you lock in these details. You practice writing the state definition, the transition loop, and the overlap guard from memory at increasing intervals. After a few rounds, you do not need to rederive the approach. You see "two agents, one grid, simultaneous movement" and the dp[c1][c2] template is already at your fingertips.
Related posts
- Coin Change - Foundation of bottom-up DP with optimal substructure, the same fill-and-lookup pattern used here
- Maximum Product Subarray - Tracking multiple values (max and min) at each step, similar to tracking two robot positions
- Minimum Path Sum - Classic grid DP with a single agent, the single-robot version of this problem's pattern
CodeBricks breaks Cherry Pickup II into its multi-dimensional state definition and paired transition building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a multi-agent DP problem appears in your interview, you do not hesitate. You define the state, enumerate the transitions, and fill the table.