Dynamic Programming • Multi-Dimensional

Cherry Pickup

Collect maximum cherries going from (0,0) to (N-1,N-1) and back. We can model this as two people starting at (0,0) simultaneously.

Try Interactive Simulator

Overview

Instead of finding a path down and a path up, we imagine two agents starting at (0,0) and walking to (N-1,N-1) simultaneously.

State Reduction

Since they move at the same speed, after `t` steps, `r1 + c1 = r2 + c2 = t`. Thus, we only need to track `r1` and `r2` for the current step `t`.

Transitions

From the previous step `t-1`, there are 4 possible moves to reach `(r1, c1)` and `(r2, c2)`: (Right, Right), (Down, Right), (Right, Down), (Down, Down).

Key Insight

If `r1 == r2` (and thus `c1 == c2`), they are on the same cell, so we only add the cherry once. Otherwise, we add cherries from both cells.

Grid (3x3): 0=empty, 1=cherry, -1=thorn

🍒

🌵

🍒

🌵

🍒

dp[r1][r2] (Step 0)

0

X

X

X

X

X

X

X

X

Code Tracker

:::

1let dp = Array(N).fill().map(() => Array(N).fill(-Infinity));

2dp[0][0] = grid[0][0];

3for (let t = 1; t <= 2*N - 2; t++) {

4 let nextDp = Array(N).fill().map(() => Array(N).fill(-Infinity));

5 // iterate r1 and r2 within bounds for step t...

6 // compute c1 = t - r1, c2 = t - r2

7 // handle thorns and add cherries (only once if r1 == r2)

8 // maxPrev = max of 4 previous states

9 // nextDp[r1][r2] = maxPrev + currentCherry;

10 dp = nextDp;

11}