Cherry Pickup
Problem
n x n field has cells that are empty (0), hold a cherry
(1) or are blocked by a thorn (-1). Walk from the top-left to the
bottom-right moving only right/down, then walk back moving only left/up,
never entering thorns. A cherry is picked the first time its cell is visited. Return the
most cherries you can collect, or 0 if the corner is unreachable.[[0,1,-1],[1,0,-1],[1,1,1]]Output5[[1,1,-1],[1,-1,1],[-1,1,1]]Output0 (no path to the corner)1 ≤ n ≤ 50 · grid[i][j] ∈ {-1, 0, 1} · start and end cells are never thorns
Try it yourself
class Solution {
public int cherryPickup(int[][] grid) {
}
}
t steps both satisfy r + c = t, so the state is
(t, r1, r2), and a shared cell is detected simply by r1 == r2.Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.
Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.
Open the Grid DP guide →Approaches
Brute ForceTwo Walkers, Plain Recursion
O(42n)Space O(n)Move both walkers one step at a time (4 combinations of down/right). Both are
always on the same anti-diagonal, so c2 = r1 + c1 - r2. Collect the
cherries under them, counting a shared cell once, and take the best continuation.
private static final int NEG = Integer.MIN_VALUE / 2; // "impossible" public int cherryPickup(int[][] grid) { return Math.max(0, walk(grid, 0, 0, 0)); } // Walker 1 at (r1, c1), walker 2 at (r2, r1 + c1 - r2); both move toward the corner private int walk(int[][] grid, int r1, int c1, int r2) { int n = grid.length, c2 = r1 + c1 - r2; if (r1 >= n || c1 >= n || r2 >= n || c2 >= n) return NEG; if (grid[r1][c1] == -1 || grid[r2][c2] == -1) return NEG; int here = grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0); // same cell counts once if (r1 == n - 1 && c1 == n - 1) return here; int best = Math.max( Math.max(walk(grid, r1 + 1, c1, r2 + 1), walk(grid, r1 + 1, c1, r2)), Math.max(walk(grid, r1, c1 + 1, r2 + 1), walk(grid, r1, c1 + 1, r2))); return best == NEG ? NEG : here + best; }
Correct modelling of the problem, but tries every pair of paths.
BetterMemoized Two-Walker DP
O(n3)Space O(n3)The recursion depends only on (r1, c1, r2) — at most
n3 states, each with 4 transitions. Cache each state the first
time it is solved.
private static final int NEG = Integer.MIN_VALUE / 2; private static final int UNSET = Integer.MIN_VALUE; public int cherryPickup(int[][] grid) { int n = grid.length; int[][][] memo = new int[n][n][n]; for (int[][] plane : memo) for (int[] row : plane) Arrays.fill(row, UNSET); return Math.max(0, walk(grid, 0, 0, 0, memo)); } private int walk(int[][] grid, int r1, int c1, int r2, int[][][] memo) { int n = grid.length, c2 = r1 + c1 - r2; if (r1 >= n || c1 >= n || r2 >= n || c2 >= n) return NEG; if (grid[r1][c1] == -1 || grid[r2][c2] == -1) return NEG; if (memo[r1][c1][r2] != UNSET) return memo[r1][c1][r2]; int here = grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0); int result; if (r1 == n - 1 && c1 == n - 1) { result = here; } else { int downDown = walk(grid, r1 + 1, c1, r2 + 1, memo); int downRight = walk(grid, r1 + 1, c1, r2, memo); int rightDown = walk(grid, r1, c1 + 1, r2 + 1, memo); int rightRight = walk(grid, r1, c1 + 1, r2, memo); int best = Math.max(Math.max(downDown, downRight), Math.max(rightDown, rightRight)); result = best == NEG ? NEG : here + best; } memo[r1][c1][r2] = result; return result; }
Fast enough for n = 50, but allocates a full n3 cube.
OptimalBottom-Up by Step, Rolling 2-D Table
O(n3)Space O(n2)Process the steps t = 0..2n-2 in order. dp[r1][r2] holds
the best total after t steps with the walkers in rows r1,
r2; step t only reads step t-1, whose four
predecessors are (r1 or r1-1) × (r2 or r2-1).
public int cherryPickup(int[][] grid) { int n = grid.length; final int NEG = Integer.MIN_VALUE / 2; int[][] dp = new int[n][n]; // dp[r1][r2] for the current step for (int[] row : dp) Arrays.fill(row, NEG); dp[0][0] = grid[0][0]; for (int t = 1; t <= 2 * n - 2; t++) { int[][] next = new int[n][n]; for (int[] row : next) Arrays.fill(row, NEG); int lo = Math.max(0, t - (n - 1)), hi = Math.min(n - 1, t); for (int r1 = lo; r1 <= hi; r1++) { for (int r2 = lo; r2 <= hi; r2++) { int c1 = t - r1, c2 = t - r2; if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue; int best = dp[r1][r2]; // both moved right if (r1 > 0) best = Math.max(best, dp[r1 - 1][r2]); if (r2 > 0) best = Math.max(best, dp[r1][r2 - 1]); if (r1 > 0 && r2 > 0) best = Math.max(best, dp[r1 - 1][r2 - 1]); if (best < 0) continue; // unreachable next[r1][r2] = best + grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0); } } dp = next; } return Math.max(0, dp[n - 1][n - 1]); }
Same time as memoization, no recursion, and only two n × n layers.
r1 ≤ r2
to halve the work — mention it, but only code it if asked.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Two Walkers, Plain Recursion | O(42n) | O(n) |
| Better | Memoized Two-Walker DP | O(n3) | O(n3) |
| Optimal | Bottom-Up by Step, Rolling 2-D Table | O(n3) | O(n2) |
- Two greedy passes (best path, clear it, best path again) — can miss the optimum.
- Counting a cherry twice when both walkers stand on the same cell.
- Returning a negative sentinel when the corner is unreachable — the answer must be 0.
- Show a counter-example to the two-greedy-passes idea before proposing the DP.
- Explain why reversing the return trip turns it into a second forward walk.
- Derive the state reduction:
c = t - rdrops one dimension from (r1,c1,r2,c2).