Cherry Pickup
Problem Statement
You are given an n x n grid. Each cell is 1 for a cherry, 0 for empty, or -1 for a thorn that cannot be crossed. Starting at the top-left cell, move only right or down to reach the bottom-right cell, then return to the top-left cell by moving only left or up. Collect cherries along the way, and a cherry can be collected at most once. Return the maximum cherries collectable. If no valid round trip exists, return 0.
Input
A square integer grid containing cherries, empty cells, and blocked thorn cells.
Output
An integer: the maximum number of cherries collectable over a valid trip from start to end and back, or 0 if no valid trip exists.
Constraints
- •
n == grid.length - •
n == grid[i].length - •
1 <= n <= 50 - •
grid[i][j] is -1, 0, or 1 - •
grid[0][0] is not -1 - •
grid[n - 1][n - 1] is not -1
Examples
Example 1
grid = [[0,1,-1],[1,0,-1],[1,1,1]]
5Example 2
grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
0Example 3
grid = [[1,1],[1,1]]
4Learning Objectives
- Reformulate a go-and-return path as two simultaneous forward paths.
- Derive one coordinate from the shared step count to reduce a 4D state to 3D.
- Handle blocked cells and same-cell collisions inside the transition.
- Use a negative sentinel for impossible DP states and clamp the final answer to zero.
Intuition
The direct story is awkward: one path goes from top-left to bottom-right, then another path comes back and must remember which cherries were already taken. That sounds like the first path changes the grid for the second path, which is too much state.
Reverse the return trip. A path that returns from bottom-right to top-left using left and up is the same sequence, reversed, as a path from top-left to bottom-right using right and down. So instead of one person going out and back, imagine two people walking from the top-left to the bottom-right at the same time.
After t moves, both people have taken exactly t steps, so if person one is at (r1, c1) and person two is at (r2, c2), then r1 + c1 = r2 + c2 = t. This lets us derive c2 from t and r2, avoiding a full four-dimensional table. When both people stand on the same cell, count its cherry once; otherwise count both cells. Thorn cells make that state impossible.
Common mistakes
- ×Trying to greedily choose the first trip and then solve the return trip on the modified grid.
- ×Using four independent coordinates even though the two walkers always share the same step count.
- ×Double-counting a cherry when both walkers land on the same cell at the same step.
- ×Allowing transitions through cells with value -1 or through coordinates outside the grid.
- ×Returning a negative sentinel when no complete path exists instead of returning 0.
State Definition
Let t = r1 + c1 = r2 + c2 be the number of steps both walkers have taken. Define dp[r1][c1][r2] as the maximum cherries collected after t steps when walker one is at (r1, c1) and walker two is at (r2, c2), where c2 = t - r2. Invalid coordinates, thorn cells, and unreachable states are treated as impossible.
State Transition
At the previous step, each walker came either from above or from the left. Therefore each state considers four predecessor pairs:
- walker one from above, walker two from above
- walker one from above, walker two from left
- walker one from left, walker two from above
- walker one from left, walker two from left
Let gain be grid[r1][c1] plus grid[r2][c2] if the two cells are different, or just one copy if they are the same cell. Then:
dp[r1][c1][r2] = gain + max(valid predecessor states)
Base case: both walkers start at (0, 0), so dp[0][0][0] = grid[0][0]. The answer is max(0, dp[n - 1][n - 1][n - 1]).
Solutions
Solution: Step-by-step DP with two walkers
Use this for the original Cherry Pickup constraints. It keeps the 3D state idea but stores only the previous step and current step, reducing memory to O(n^2).
Process the two walkers by shared step count. For each step, enumerate valid rows for walker one and walker two, derive both columns, skip thorns, then combine the best of the four predecessor row pairs with the cherries gained at the current cells.
Step-by-step
- If the start or end is blocked, no round trip is possible.
- Store DP for the previous shared step as a 2D table indexed by the two row positions.
- For each step from 1 to 2n - 2, create a fresh current table filled with a large negative impossible value.
- Enumerate row1 and row2 values that keep derived columns inside the grid.
- Skip states where either cell is a thorn, take the best predecessor among four move combinations, add one or two cherries, and save the result.
- After the final step, clamp the destination value at zero.
O(n^3)
O(n^2)
There are O(n) step layers, each with O(n^2) row-pair states and O(1) transition work.
Java implementation
Dry Run
Sample input
grid = [[0,1,-1],[1,0,-1],[1,1,1]]. One optimal pair of simultaneous paths is shown, with both walkers taking the same step number.
| step | walker one | walker two | cherries added | best total |
|---|---|---|---|---|
| 0 | (0,0) | (0,0) | 0, same cell | 0 |
| 1 | (1,0) | (0,1) | 1 + 1 | 2 |
| 2 | (2,0) | (1,1) | 1 + 0 | 3 |
| 3 | (2,1) | (2,1) | 1, same cell | 4 |
| 4 | (2,2) | (2,2) | 1, same cell | 5 |
The two walkers represent the outgoing trip and the reversed return trip. Shared cells are counted once, so the best total for the round trip is 5 cherries.
Complexity Analysis
The full conceptual state is 3D, but iterating by shared step lets the implementation store only two O(n^2) layers. Time remains O(n^3), which fits n up to 50.
Step-by-step DP with two walkers
O(n^3)
O(n^2)
There are O(n) step layers, each with O(n^2) row-pair states and O(1) transition work.
Interview Tips
Spend time on the reformulation before writing the recurrence. Say: the return path reversed is another forward path, so two walkers move together from the start. Then derive c2 from the shared step count. This explanation usually matters more than the code mechanics.
Likely follow-ups
- How would the solution change for Cherry Pickup II, where two robots start in different columns of the top row?
- Can you return the actual two paths that collect the maximum cherries?
- What if cells contained arbitrary non-negative cherry counts instead of only 0 or 1?
- How would obstacles that change over time affect the state definition?
Similar Problems
Key Takeaways
- A go-and-return path can often be modelled as two forward paths moving simultaneously.
- Shared step count removes one coordinate from a two-agent grid state.
- When two agents visit the same cell at the same time, count the reward once.
- Impossible states should use a negative sentinel and never participate in valid transitions.