DSA Tracker

Visualize

Cherry Pickup II

Two synchronized walkers: dp[step][r1][r2], each cell collected only once

time O(n^3)space O(n^2)

A round trip is exactly the same as sending two people forward from (0,0) to the bottom-right corner at the same time, then adding up what they collect (paying a cell only once if both walkers land on it). Every monotone path uses the same number of moves, so "same time" just means "same step count" — that's what lets dp[step][r1][r2] work: r2 is implied by c2 = step - r2, so the whole state is really only 3 numbers deep, not 4.

Details

Animated on: A 5x5 grid of cherries (0, 1 for a cherry, or -1 for a thorn). Walk from (0,0) to (4,4) and back, collecting the max cherries; each cell can only be collected once.

Problem:Cherry Pickup IIHard

Two synchronized walkers: dp[step][r1][r2], each cell collected only once

step 1 / 9

Chocolate Pickup on a 5x5 grid — collect the max walking (0,0) -> (4,4) and back

A round trip and back is the same as two people walking forward from (0,0) to (4,4) at the same time — every monotone path takes exactly 8 moves, so "same time" always means "same move count". Both start on 1.

Pseudocode
1FUNCTION cherryPickup(grid):
2  n <- LENGTH(grid)
3  dp[0][0][0] <- grid[0][0]
4  FOR step FROM 1 TO 2*(n-1):
5    FOR EACH valid (r1, r2) pair FOR step:
6      c1 <- step - r1
7      c2 <- step - r2
8      IF grid[r1][c1] = -1 OR grid[r2][c2] = -1: CONTINUE
9      best <- MAX(dp[step-1][r1-a][r2-b]) OVER a, b IN {0,1}
10      IF best = -INF: CONTINUE
11      gain <- grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0)
12      dp[step][r1][r2] <- best + gain
13  RETURN MAX(0, dp[2*(n-1)][n-1][n-1])

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. A round trip and back is the same as two people walking forward from (0,0) to (4,4) at the same time — every monotone path takes exactly 8 moves, so "same time" always means "same move count". Both start on 1.
  2. Move 1/8: walker 1 -> (1,0), walker 2 -> (0,1), adding 1 this step.
  3. Move 2/8: walker 1 -> (2,0), walker 2 -> (0,2), adding 2 this step.
  4. Move 3/8: walker 1 -> (2,1), walker 2 -> (0,3), adding 2 this step.
  5. Move 4/8: walker 1 -> (3,1), walker 2 -> (1,3), adding 2 this step.
  6. Move 5/8: walker 1 -> (4,1), walker 2 -> (2,3), adding 2 this step.
  7. Move 6/8: walker 1 -> (4,2), walker 2 -> (3,3), adding 2 this step.
  8. Move 7/8: walker 1 -> (4,3), walker 2 -> (4,3), adding 1 this step. They land on the same cell, so its 1 counts once.
  9. Both walkers reach (4,4) on move 8/8. Total collected: 14 cherries.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Cherry Pickup II in the editorAll Dynamic Programming problemsBack to roadmap