Cherry Pickup
Max cherries on two paths from top-left to bottom-right then back — simulate two simultaneous downward paths in 3D DP.
7 min read
dp grid
Problem#
Grid: 0 empty, 1 cherry, -1 thorn. Walk top-left → bottom-right (right/down) collecting cherries; then bottom-right → top-left (left/up). Pickup any cell once. Max cherries collected.
Hints#
Hint 1
Equivalent to two simultaneous walkers from top-left to bottom-right. After
k steps, both are on the anti-diagonal r + c = k. Approach#
3D DP dp[r1][r2] (with c1 = step - r1, c2 = step - r2). For each step k = 0..2n-2, both walkers are at total Manhattan distance k from origin. Transition: each walker came from “right” or “down” — 4 combinations. If they’re at the same cell, count cherry once.
Solution#
class Solution {public: int cherryPickup(vector<vector<int>>& grid) { int n = grid.size(); vector<vector<int>> dp(n, vector<int>(n, INT_MIN)); dp[0][0] = grid[0][0]; for (int k = 1; k <= 2 * (n - 1); ++k) { vector<vector<int>> nd(n, vector<int>(n, INT_MIN)); for (int r1 = max(0, k - (n - 1)); r1 <= min(n - 1, k); ++r1) { for (int r2 = max(0, k - (n - 1)); r2 <= min(n - 1, k); ++r2) { int c1 = k - r1, c2 = k - r2; if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue; int best = INT_MIN; for (int dr1 : {0, 1}) for (int dr2 : {0, 1}) { int pr1 = r1 - dr1, pr2 = r2 - dr2; if (pr1 < 0 || pr2 < 0) continue; if (dp[pr1][pr2] != INT_MIN) best = max(best, dp[pr1][pr2]); } if (best == INT_MIN) continue; int add = grid[r1][c1]; if (r1 != r2) add += grid[r2][c2]; nd[r1][r2] = best + add; } } dp = nd; } return max(dp[n - 1][n - 1], 0); }};func cherryPickup(grid [][]int) int { n := len(grid) NEG := math.MinInt32 dp := make([][]int, n) for i := range dp { dp[i] = make([]int, n) for j := range dp[i] { dp[i][j] = NEG } } dp[0][0] = grid[0][0] for k := 1; k <= 2*(n-1); k++ { nd := make([][]int, n) for i := range nd { nd[i] = make([]int, n) for j := range nd[i] { nd[i][j] = NEG } } lo := k - (n - 1) if lo < 0 { lo = 0 } hi := k if hi > n-1 { hi = n - 1 } for r1 := lo; r1 <= hi; r1++ { for r2 := lo; r2 <= hi; r2++ { c1, c2 := k-r1, k-r2 if grid[r1][c1] == -1 || grid[r2][c2] == -1 { continue } best := NEG for _, dr1 := range []int{0, 1} { for _, dr2 := range []int{0, 1} { pr1, pr2 := r1-dr1, r2-dr2 if pr1 < 0 || pr2 < 0 { continue } if dp[pr1][pr2] != NEG && dp[pr1][pr2] > best { best = dp[pr1][pr2] } } } if best == NEG { continue } add := grid[r1][c1] if r1 != r2 { add += grid[r2][c2] } nd[r1][r2] = best + add } } dp = nd } if dp[n-1][n-1] < 0 { return 0 } return dp[n-1][n-1]}from typing import List
class Solution: def cherryPickup(self, grid: List[List[int]]) -> int: n = len(grid) NEG = float('-inf') dp = [[NEG] * n for _ in range(n)] dp[0][0] = grid[0][0] for k in range(1, 2 * (n - 1) + 1): nd = [[NEG] * n for _ in range(n)] lo = max(0, k - (n - 1)) hi = min(n - 1, k) for r1 in range(lo, hi + 1): for r2 in range(lo, hi + 1): c1, c2 = k - r1, k - r2 if grid[r1][c1] == -1 or grid[r2][c2] == -1: continue best = NEG for dr1 in (0, 1): for dr2 in (0, 1): pr1, pr2 = r1 - dr1, r2 - dr2 if pr1 < 0 or pr2 < 0: continue if dp[pr1][pr2] != NEG and dp[pr1][pr2] > best: best = dp[pr1][pr2] if best == NEG: continue add = grid[r1][c1] if r1 != r2: add += grid[r2][c2] nd[r1][r2] = best + add dp = nd return max(dp[n - 1][n - 1], 0)var cherryPickup = function(grid) { const n = grid.length; const NEG = -Infinity; let dp = Array.from({ length: n }, () => new Array(n).fill(NEG)); dp[0][0] = grid[0][0]; for (let k = 1; k <= 2 * (n - 1); k++) { const nd = Array.from({ length: n }, () => new Array(n).fill(NEG)); const lo = Math.max(0, k - (n - 1)); const hi = Math.min(n - 1, k); for (let r1 = lo; r1 <= hi; r1++) { for (let r2 = lo; r2 <= hi; r2++) { const c1 = k - r1, c2 = k - r2; if (grid[r1][c1] === -1 || grid[r2][c2] === -1) continue; let best = NEG; for (const dr1 of [0, 1]) { for (const dr2 of [0, 1]) { const pr1 = r1 - dr1, pr2 = r2 - dr2; if (pr1 < 0 || pr2 < 0) continue; if (dp[pr1][pr2] !== NEG && dp[pr1][pr2] > best) { best = dp[pr1][pr2]; } } } if (best === NEG) continue; let add = grid[r1][c1]; if (r1 !== r2) add += grid[r2][c2]; nd[r1][r2] = best + add; } } dp = nd; } return Math.max(dp[n - 1][n - 1], 0);};class Solution { public int cherryPickup(int[][] grid) { int n = grid.length; final int NEG = Integer.MIN_VALUE; int[][] dp = new int[n][n]; for (int[] row : dp) Arrays.fill(row, NEG); dp[0][0] = grid[0][0]; for (int k = 1; k <= 2 * (n - 1); k++) { int[][] nd = new int[n][n]; for (int[] row : nd) Arrays.fill(row, NEG); int lo = Math.max(0, k - (n - 1)); int hi = Math.min(n - 1, k); for (int r1 = lo; r1 <= hi; r1++) { for (int r2 = lo; r2 <= hi; r2++) { int c1 = k - r1, c2 = k - r2; if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue; int best = NEG; for (int dr1 = 0; dr1 <= 1; dr1++) { for (int dr2 = 0; dr2 <= 1; dr2++) { int pr1 = r1 - dr1, pr2 = r2 - dr2; if (pr1 < 0 || pr2 < 0) continue; if (dp[pr1][pr2] != NEG && dp[pr1][pr2] > best) { best = dp[pr1][pr2]; } } } if (best == NEG) continue; int add = grid[r1][c1]; if (r1 != r2) add += grid[r2][c2]; nd[r1][r2] = best + add; } } dp = nd; } return Math.max(dp[n - 1][n - 1], 0); }}function cherryPickup(grid: number[][]): number { const n = grid.length; const NEG = -Infinity; let dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(NEG)); dp[0][0] = grid[0][0]; for (let k = 1; k <= 2 * (n - 1); k++) { const nd: number[][] = Array.from({ length: n }, () => new Array(n).fill(NEG)); const lo = Math.max(0, k - (n - 1)); const hi = Math.min(n - 1, k); for (let r1 = lo; r1 <= hi; r1++) { for (let r2 = lo; r2 <= hi; r2++) { const c1 = k - r1, c2 = k - r2; if (grid[r1][c1] === -1 || grid[r2][c2] === -1) continue; let best = NEG; for (const dr1 of [0, 1]) { for (const dr2 of [0, 1]) { const pr1 = r1 - dr1, pr2 = r2 - dr2; if (pr1 < 0 || pr2 < 0) continue; if (dp[pr1][pr2] !== NEG && dp[pr1][pr2] > best) { best = dp[pr1][pr2]; } } } if (best === NEG) continue; let add = grid[r1][c1]; if (r1 !== r2) add += grid[r2][c2]; nd[r1][r2] = best + add; } } dp = nd; } return Math.max(dp[n - 1][n - 1], 0);}Editorial#
The two-walker reformulation is the key trick — return paths in the original problem map to a second forward walker. Sharing the time k = r + c reduces dimensionality by one (we only need r1, r2; columns follow).
Complexity#
- Time: O(n³).
- Space: O(n²).
Concept revision#
Related#