Pattern visualizer
Chocolate Pickup (3D DP)
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. 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..
Two synchronized walkers: dp[step][r1][r2], each cell collected only once
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.
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 - r17 c2 <- step - r28 IF grid[r1][c1] = -1 OR grid[r2][c2] = -1: CONTINUE9 best <- MAX(dp[step-1][r1-a][r2-b]) OVER a, b IN {0,1}10 IF best = -INF: CONTINUE11 gain <- grid[r1][c1] + (r1 != r2 ? grid[r2][c2] : 0)12 dp[step][r1][r2] <- best + gain13 RETURN MAX(0, dp[2*(n-1)][n-1][n-1])
← / → step · space play · Home restart