Problem Statement

Cherry Pickup

You have a square grid (the same number of rows and columns). Each cell holds one of three things: a cherry (written as 1), an empty space (written as 0), or a thorn (written as -1) that you cannot walk through. You start at the top-left corner (0,0), walk to the bottom-right corner (n-1,n-1) picking up cherries, then walk back to the start picking up more. On the way down you can only move right or down, and on the way back you can only move left or up. You collect a cherry the first time you step on it, and the cell becomes empty after that. The goal is to collect the most cherries possible. Here is the clever idea: walking there and then back is the same as sending TWO people from (0,0) to (n-1,n-1) at the same time, both moving only right or down. Both walkers take the same number of moves, exactly (n-1) + (n-1) steps. We track the problem by step number. At step t, walker 1 sits at (r1, t-r1) and walker 2 sits at (r2, t-r2). That lets us solve it with dynamic programming, which means we break the trip into smaller positions, solve each once, and remember the answer so we never redo it.

hardDynamic ProgrammingGridDynamic ProgrammingTime: O(n³) · Space: O(n³)

Signals to notice

two paths collecting cherriessimultaneous traversalcan't double-count

Brute force first

Two-pass greedy — provably suboptimal.

The key insight

3D DP: both paths move simultaneously. dp[step][c1][c2]. If same cell, count once. O(n³).

Trace it on `grid=[[0,1,-1],[1,0,-1],[1,1,1]], n=3`

dp(0,0,0): same cell (0,0)=0 counted once → gain 0; branch on 4 moves
Best move: P1 down to (1,0), P2 right to (0,1) → dp(1,0,0)
dp(1,0,0): c2=1 → P1@(1,0)=1, P2@(0,1)=1, distinct → gain 2
→ dp(2,0,0): c2=2 → P1@(2,0)=1, P2@(0,2)=-1 thorn → -INF (pruned)
Better: dp(1,0,0)→ P1 down (2,0), P2 down (1,1) → dp(2,0,1)
dp(2,0,1): c2=1 → P1@(2,0)=1, P2@(1,1)=0 → gain 1; then both funnel to (2,1)/(2,2)
Path converges: collect (2,1)=1 and shared (2,2)=1 once → remaining 2
dp(0,0,0)=0 +2 +1 +2 = 5; return max(0,5) = 5

What must stay true

Simultaneous movement with same step count: r1+c1 = r2+c2. If same cell, cherries counted once.

Shape of the loop

def dp(r1, c1, r2):           # c2 = r1 + c1 - r2  (same step ⇒ same diagonal)
    if out_of_bounds or thorn:  return -INF
    if (r1,c1) == (n-1,n-1):    return grid[r1][c1]
    gain = grid[r1][c1] + (grid[r2][c2] if (r1,c1) != (r2,c2) else 0)
    return gain + max(dp(r1+1,c1,r2+1), dp(r1+1,c1,r2),
                      dp(r1,c1+1,r2+1), dp(r1,c1+1,r2))   # memoize
# answer = max(0, dp(0,0,0))

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Two-pass greedy is WRONG — must optimize both paths jointly.

Dynamic Programming Pattern