Cherry Pickup
Understanding the Problem
This reads like two separate path problems: go from top-left to bottom-right collecting cherries, then come back collecting more. The trips are not independent, though. Cherries picked on the first trip disappear, so the second trip sees a modified grid, and maximizing each trip on its own can lock in a suboptimal total.
Instead of one trip forward and one trip back, model the round trip as two people walking simultaneously from (0, 0) to (n-1, n-1). Person 1 represents the forward trip. Person 2 represents the return trip, reversed so it also runs top-left to bottom-right. Both move one step at a time, either right or down, and a cherry on a cell both occupy is counted once. This reformulation turns a sequential problem with interacting trips into a single DP over both walkers' positions.
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
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, then find a second maximum-cherry path on the modified grid (a return trip is equivalent to another forward trip with the moves reversed).
Each trip on its own is a standard maximum-path-sum DP, so this is easy to implement. It is also wrong. The best single path can take cherries positioned so that whatever remains cannot be covered by one more right/down path, while two coordinated paths, each individually suboptimal, collect more in total. The walkthrough below shows a grid where this happens.
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.
On the walkthrough grid, the greedy split collects 4 cherries while the true maximum is 5. No fix to the first trip repairs this, because the two paths have to be chosen together. The next approach optimizes them as a single decision.
Approach 2: 3D DP (Two Simultaneous Walkers)
Intuition
Reversing the return trip makes the two-walker model exact: a path from (n-1,n-1) to (0,0) using left and up moves, read backwards, is a path from (0,0) to (n-1,n-1) using right and down moves, and it visits the same cells. The round trip is therefore two forward paths, chosen together.
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.
Cherry collection follows one rule: if both walkers are on the same cell, the cherry is counted once; otherwise each walker collects its own cell. This single rule is enough to prevent any cherry from being counted twice across the whole round trip.
The same-cell check catches every possible double count, not only collisions that happen to occur at the same moment. Any right/down path reaches cell (r, c) after exactly r + c moves. So if both walkers' paths pass through a cell, they occupy it at the same step t = r + c, never at different times. Checking r1 == r2 at each step (with t fixed, equal rows mean equal columns) therefore detects every shared cell.
The reformulation is also exact in the other direction: every pair of forward paths corresponds to a valid round trip and collects the cherries on the union of the two paths, which is precisely the quantity to maximize.
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.
- After the final step
t = 2*(n-1), both walkers are at (n-1, n-1), so the answer isdp[n-1][n-1]. If it is still negative, no valid path pair exists; return 0. (Each step only reads the previous step's values, so the implementation keeps two 2D arrays instead of a full 3D table.)
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 same recurrence can also be written top down. Recursion with memoization removes the manual loop bounds and buffer swapping, at the cost of an O(n^3) memo table instead of two O(n^2) arrays.
Approach 3: Top-Down Memoization
Intuition
The top-down version asks, from a given pair of positions, what is the best both walkers can still collect on the way to (n-1, n-1). Define a function solve(r1, c1, r2) that returns that maximum. Both walkers have taken the same number of steps, so c2 = r1 + c1 - r2 and does not need to be passed. Each call tries the 4 movement combinations (each walker goes right or down) and takes the maximum over the valid ones.
Algorithm
- Define
solve(r1, c1, r2)wherec2 = r1 + c1 - r2. - If any position is out of bounds or a thorn, return negative infinity.
- Base case: if
r1 == n-1andc1 == n-1, walker 1 is at the destination, and so is walker 2: the bounds check already passed, andc2 = 2*(n-1) - r2 <= n-1forcesr2 = n-1. Returngrid[n-1][n-1], counted once. - 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.