DSA problem
Cherry Pickup
You are given an n x n grid containing 0 (empty cell), 1 (cherry), or -1 (thorn). Start at (0, 0), travel to (n - 1, n - 1) moving only right or down, collecting any cherries on the path (clearing them to 0), and then travel back to (0, 0) moving only left or up, collecting any remaining cherries. Thorns are impassable. Return the maximum total cherries you can collect; if it is impossible to make the round trip, return 0.
A return trip moving only left/up is equivalent to a second forward trip moving only right/down (just reverse it). So the problem is: simulate two simultaneous forward walkers from (0, 0) to (n - 1, n - 1) that share cherry pickups — if both step on the same cell only one cherry is collected. Maximize total cherries.
Let the two walkers be at the same time step t at positions (r1, c1) and (r2, c2) with r1 + c1 = r2 + c2 = t. So c1 and c2 determine r1 and r2 given t. Define dp[t][c1][c2] = max cherries collected to bring both walkers to step t at columns c1 and c2. Each walker has 2 move choices, so each transition combines 4 prior states.
The pickup rule: add grid[r1][c1], plus grid[r2][c2] only when (r1, c1) != (r2, c2). Forbid thorns by returning -inf from those states. The answer is max(0, dp[2n - 2][n - 1][n - 1]). Implementations typically use a 2-D dp indexed by (c1, c2) with t implicit, giving O(n^3) time and O(n^2) space.
Examples
grid = [[0,1,-1],[1,0,-1],[1,1,1]]5grid = [[1,1,-1],[1,-1,1],[-1,1,1]]0grid = [[1]]1Constraints
- n == grid.length == grid[i].length
- 1 <= n <= 50
- grid[i][j] is one of -1, 0, or 1.
- grid[0][0] != -1 and grid[n - 1][n - 1] != -1.
- You may move only right or down on the forward trip (left or up on the return).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.