Cherry Pickup LeetCode 741 — 3D DP Guide

LeetCode 741 Cherry Pickup presents an n x n grid where each cell contains one of three values: 1 (a cherry), 0 (empty), or -1 (a thorn that blocks movement). Starting at the top-left corner (0, 0), you must walk to the bottom-right corner (n-1, n-1) collecting cherries, then return to (0, 0) along any valid path. Each cherry can only be collected once — if you collect a cherry on the way forward, the cell becomes empty for the return trip. Your goal is to maximize the total number of cherries collected across both trips.

You may only move right or down on the forward trip, and only left or up on the return trip. If any cell on your path contains -1, that path is invalid. If no valid round trip exists (because thorns block all paths from start to end), the answer is 0. The constraint that movement is restricted to right/down on the forward leg and left/up on the return leg means both trips collectively cover exactly 2*(n-1) steps each.

The problem is harder than it appears. The round-trip structure means the forward path and return path are not independent — they share the same grid, and cherries collected on one trip are gone for the other. This interaction is what makes a simple greedy or two-pass DP approach incorrect.

The most intuitive approach is greedy: find the path from (0,0) to (n-1,n-1) that collects the most cherries, mark those cherries as collected, then find the best path back. This seems reasonable — you are trying to maximize total cherries, so maximizing on each trip independently sounds correct. However, this greedy strategy can produce suboptimal results because the two trips are coupled through the shared grid.

Consider a grid where two high-cherry paths diverge and converge. The greedy forward path picks one branch, collecting all cherries on it. The return path is then forced onto the other branch, which has fewer cherries. But if both trips had taken different routes — each getting a moderate share of cherries from both branches — the total would be higher. The greedy approach fails because optimizing trip 1 in isolation changes the grid state for trip 2, and the combined optimum is not the sum of two individual optima.

This is a classic example where a local greedy choice (maximizing forward cherries) undermines the global objective (maximizing total cherries). The key insight needed to solve this problem correctly is to stop thinking about a forward trip followed by a return trip, and instead reframe the problem as a single joint optimization over both trips simultaneously.

Once we reframe the problem as two people both walking from (0,0) to (n-1,n-1) simultaneously, a powerful structural observation emerges: since both walkers only move right or down, after t steps each walker has taken exactly t moves. If walker 1 is at row r1, they have made r1 down-moves and (t - r1) right-moves, so their column is c1 = t - r1. Similarly, walker 2 at row r2 has column c2 = t - r2. Both c1 and c2 are fully determined by t, r1, and r2.

This means at any step t, the entire joint state of both walkers is captured by just three numbers: (r1, r2, t) — or equivalently (r1, c1, r2) since t = r1 + c1. We do not need to store c1 and c2 separately because they are derived quantities. This observation collapses what would otherwise be a 4D DP over (r1, c1, r2, c2) down to a 3D DP over (r1, r2, t), reducing both time and space complexity significantly.

At each step t, both walkers independently choose to move right or down. There are 2 choices for walker 1 and 2 choices for walker 2, giving 4 possible combined moves: (down, down), (down, right), (right, down), (right, right). We try all 4 transitions and keep the best. When both walkers land on the same cell (r1 == r2, which implies c1 == c2 since t is shared), the cherry on that cell is counted only once in the reward.

Define dp[r1][r2] at step t as the maximum cherries collectible by two walkers where walker 1 is at (r1, t-r1) and walker 2 is at (r2, t-r2), having both started at (0,0) and taken t steps. The value is -infinity if either position is invalid (out of bounds or on a thorn). We want the answer at t = 2*(n-1), which is dp[n-1][n-1] (both walkers at the bottom-right corner).

The transition at step t is: dp_next[r1][r2] = max over (dr1, dr2) in {(0,1),(1,0)} x {(0,1),(1,0)} of (dp[r1][r2] + cherries_at(r1_new, c1_new) + cherries_at(r2_new, c2_new)). The cherry reward is grid[r1_new][c1_new] + grid[r2_new][c2_new] unless r1_new == r2_new (same cell), in which case it is grid[r1_new][c1_new] counted once. If grid[r1_new][c1_new] == -1 or grid[r2_new][c2_new] == -1, that state is invalid (set to -infinity).

The base case is dp[0][0] = grid[0][0] at step t=0. If grid[0][0] == -1, the problem has no solution. We iterate t from 0 to 2*(n-1)-1, and at each step we compute the new dp table from the old one. Using a rolling 2D array of size n x n, the space complexity is O(n^2). Time complexity is O(n^3) since there are O(n^2) states at each of O(n) steps and each transition is O(1).

The iteration structure is: for t in range(2*(n-1)): for r1 in range(max(0, t-(n-1)), min(n-1, t)+1): for r2 in range(r1, min(n-1, t)+1): compute new dp[r1][r2] from old dp values. Note that r2 ranges from r1 to avoid double-counting symmetric states — by symmetry, the two walkers are interchangeable, so we only need r1 <= r2. The column values are c1 = t - r1 and c2 = t - r2. Both must be in [0, n-1], which the loop bounds enforce.

Thorn handling is critical: at each new state (r1_new, c1_new), check if grid[r1_new][c1_new] == -1 and mark dp_next[r1_new][r2_new] = -infinity if so. Same for walker 2. When computing the cherry reward, add grid[r1_new][c1_new] (clamped: treat -1 as invalid rather than as -1 cherries). The easiest implementation initializes all dp values to -infinity and only updates states reachable from valid prior states.

Base case: initialize a 2D array dp[n][n] = -infinity everywhere, then set dp[0][0] = grid[0][0]. If grid[0][0] == -1, immediately return 0. After completing all steps, the answer is max(0, dp[n-1][n-1]) — the max ensures we return 0 if no valid path exists (dp[n-1][n-1] remains -infinity).

Python implementation with rolling 2D DP array: def cherryPickup(grid): n = len(grid); NEG_INF = float("-inf"); dp = [[NEG_INF]*n for _ in range(n)]; dp[0][0] = grid[0][0]; for t in range(1, 2*n-1): ndp = [[NEG_INF]*n for _ in range(n)]; for r1 in range(max(0,t-n+1), min(n-1,t)+1): c1=t-r1; if c1<0 or c1>=n or grid[r1][c1]==-1: continue; for r2 in range(r1, min(n-1,t)+1): c2=t-r2; if c2<0 or c2>=n or grid[r2][c2]==-1: continue; best=NEG_INF; for dr1 in range(2): for dr2 in range(2): pr1,pc1,pr2,pc2=r1-dr1,c1-(1-dr1),r2-dr2,c2-(1-dr2); if 0<=pr1<n and 0<=pc1<n and 0<=pr2<n and 0<=pc2<n and dp[pr1][pr2]!=NEG_INF: best=max(best,dp[pr1][pr2]); if best==NEG_INF: continue; cherries=grid[r1][c1]+(0 if r1==r2 else grid[r2][c2]); ndp[r1][r2]=max(ndp[r1][r2],best+cherries); dp=ndp; return max(0, dp[n-1][n-1]). Time O(n^3), space O(n^2) using the rolling array.

Java implementation follows the same structure: initialize a 2D int array dp[n][n] filled with Integer.MIN_VALUE/2 (to avoid overflow when adding), set dp[0][0] = grid[0][0], then iterate t from 1 to 2*n-2. At each step create ndp[n][n] filled with Integer.MIN_VALUE/2 and compute transitions. The cherry reward check uses r1 == r2 to detect same-cell overlap. Return Math.max(0, dp[n-1][n-1]) after all iterations. The /2 sentinel avoids integer overflow when computing dp + reward where dp might already be a large negative sentinel value.

Both implementations use r2 >= r1 as the inner loop bound. This symmetry reduction halves the work and is safe because swapping walker 1 and walker 2 produces the same result — they are interchangeable. When reading or writing dp[r1][r2], always ensure r1 <= r2; if your transition produces r2_new < r1_new, swap them before indexing.

Cherry Pickup II (LeetCode 1463) is the direct sequel: two robots start at the top corners of a grid and move downward simultaneously, collecting cherries. The same two-walker simultaneous DP applies, but the robots move in 3 directions each (down-left, down, down-right) instead of 2. The state is again (row, col1, col2) collapsed by using the shared row, giving O(m*n^2) time. Solving LeetCode 741 first is the best preparation for LeetCode 1463.

Minimum Path Sum (LeetCode 64) and Dungeon Game (LeetCode 174) are foundational single-path grid DP problems. Minimum Path Sum minimizes the sum along a single right/down path, while Dungeon Game finds the minimum initial health needed to survive a path with negative cells. Both share the right/down movement constraint with Cherry Pickup but have only one walker and no interaction between trips. Solving them first builds the grid DP intuition before tackling the two-walker complexity of LeetCode 741.

The broader family of multi-agent grid DP includes problems where k agents move simultaneously through a grid. The general pattern is: state = (step, positions of all agents except one derived via step constraint), transitions = all combinations of moves for each agent, reward = sum of per-agent rewards with overlap deduplication. Cherry Pickup is the k=2 case. For larger k, the DP becomes O(n^(k+1)) time which quickly becomes infeasible, so such problems typically have small k or additional structural constraints that limit the state space.