Cherry Pickup
Last Updated: March 28, 2026
Understanding the Problem
At first glance, this looks like two separate path problems: go from top-left to bottom-right collecting cherries, then come back collecting more. The catch is that the two trips are not independent. Cherries picked on the first trip disappear, so the second trip sees a modified grid. A greedy approach of picking the maximum on the first trip and then again on the second does not work because it can lead to suboptimal global results.
Here is the key insight that transforms this problem: instead of thinking about one trip forward and one trip back, we can model it as two people walking simultaneously from (0, 0) to (n-1, n-1). Person 1 represents the forward trip, and Person 2 represents the return trip (reversed to also go top-left to bottom-right). Both move at the same pace, one step at a time, either right or down. If they land on the same cell, the cherry is only counted once. This "two simultaneous walkers" reformulation turns a tricky sequential problem into a clean DP problem.
Key Constraints:
1 <= n <= 50-> The grid is at most 50x50 = 2,500 cells. We have room for O(n^3) or even O(n^4) solutions.grid[i][j]is-1,0, or1-> Thorns block paths entirely, not just increase cost. We must handle unreachable states.
Approach 1: Greedy (Two Independent Trips)
Intuition
The most natural first attempt is to solve the two trips independently. Find the path from (0,0) to (n-1,n-1) that collects the most cherries, remove those cherries from the grid, and then find another max-cherry path back (which is equivalent to another forward path on the modified grid).
This feels right because each trip is a standard maximum-path-sum problem solvable with DP. But it fails because the greedy first trip can block a better global solution. The first trip's greedy choice can "steal" cherries from positions that the second trip needs, leading to a globally suboptimal total.
Algorithm
- Use DP to find the path from (0,0) to (n-1,n-1) that collects the maximum cherries.
- Mark all cherries along that path as collected (set them to 0).
- Use DP again on the modified grid to find a second maximum-cherry path.
- Return the sum of cherries from both trips.
Example Walkthrough
Code
- Time Complexity: O(n^2). Each trip requires a single pass through the n x n grid, so O(n^2) per trip and O(n^2) total.
- Space Complexity: O(n^2). We use an n x n DP table for each trip.
This approach produces incorrect results because solving two trips independently is fundamentally wrong. The first trip's greedy choice can steal cherries the second trip needs. What if we considered both trips simultaneously?
Approach 2: 3D DP (Two Simultaneous Walkers)
Intuition
The breakthrough is realizing that the round trip (forward then back) can be modeled as two people walking forward simultaneously. Person 1's path represents the original forward trip. Person 2's path represents the return trip, but reversed so it also goes from (0,0) to (n-1,n-1).
Both walkers take exactly 2*(n-1) steps total to reach the destination. At each step, each walker moves either right or down. The number of steps taken so far, call it t, determines a constraint: if a walker is at row r, their column must be c = t - r. So with t fixed, we only need to track r1 (walker 1's row) and r2 (walker 2's row) to know both positions completely.
The cherry collection works like this: if both walkers are on the same cell, the cherry is counted once. If they are on different cells, each walker picks up their own cherry independently. This naturally handles the "cherry disappears after being picked" constraint.
The simultaneous-walkers model works because of a subtle equivalence. The return trip goes from (n-1,n-1) to (0,0) moving left or up. If you reverse the direction of time, that is the same as going from (0,0) to (n-1,n-1) moving right or down. So the round trip is equivalent to two simultaneous forward trips.
The "step" parameter t acts as a clock that synchronizes both walkers. At step t, both walkers have taken exactly t moves, so row + col = t for each walker. This constraint lets us reduce the state space from 4 dimensions (r1, c1, r2, c2) to 3 dimensions (t, r1, r2), since both columns are determined.
Algorithm
- Let
trange from 0 to2*(n-1). This is the step number (how many moves each walker has made). - For each step
t, iterate over all valid (r1, r2) pairs where0 <= r1, r2 <= min(t, n-1)andc1 = t - r1andc2 = t - r2are valid column indices. - Both walkers arrived at their current position from the previous step. Each could have moved down (from row r-1) or right (from row r at previous step). This gives 4 predecessor combinations.
- Take the max over all 4 predecessor states. Add the cherries at both current positions. If both walkers are on the same cell, add the cherry value only once.
- Return dp[2*(n-1)][n-1][n-1]. If it is negative, return 0.
Example Walkthrough
Code
- Time Complexity: O(n^3). We iterate over t from 0 to 2(n-1), which is O(n) steps. At each step, we consider all (r1, r2) pairs where both range over at most n values. So it is O(n) O(n) O(n) = O(n^3).
- Space Complexity: O(n^2). We maintain two 2D arrays (dp and prev) of size n x n, swapping between them at each step.
The bottom-up approach is correct and space-efficient, but the loop bounds and swap logic can be tricky to get right. Can we express the same idea more naturally using recursion?
Approach 3: Top-Down Memoization
Intuition
A top-down recursive approach with memoization expresses the same two-walker idea more naturally: "what is the best I can do from this state?" We define a function solve(r1, c1, r2) that returns the maximum cherries collectible from the current positions to (n-1, n-1) for both walkers. Since c2 = r1 + c1 - r2, we do not need to pass c2 explicitly. At each recursive call, both walkers choose to go right or down (4 combinations), and we take the maximum over all valid choices.
Algorithm
- Define
solve(r1, c1, r2)wherec2 = r1 + c1 - r2. - Base case: if
r1 == n-1andc1 == n-1, both walkers are at the destination. Return grid[r1][c1] (counted once since both are at the same cell). - If any position is out of bounds or a thorn, return negative infinity.
- Compute cherries at current positions (once if same cell, both if different).
- Try all 4 movement combinations: (down,down), (down,right), (right,down), (right,right).
- Return current cherries + max of all 4 recursive results.
- Memoize using a 3D table indexed by (r1, c1, r2).
Example Walkthrough
Code
- Time Complexity: O(n^3). There are at most n n n = n^3 unique states (r1, c1, r2). Each state does O(1) work (4 recursive calls, each looked up in O(1) from the memo table).
- Space Complexity: O(n^3). The memoization table stores up to n^3 entries. The recursion stack depth is at most 2(n-1), which is O(n), dominated by the memo table.