p78 — Cherry Pickup

Source: LeetCode 741 · Hard · Topics: DP, Multi-Agent DP, Grid Companies (2024–2025): Google (high), Amazon (medium), Meta (medium-high) Loop position: The multi-agent DP reframing. Naive “go then return” greedy fails. The insight that “round trip” = “two simultaneous one-way trips” is the entire problem.

1. Quick Context

n×n grid. 0 = empty, 1 = cherry, -1 = thorn. Walk from (0,0) → (n-1,n-1) moving only right/down picking cherries (set to 0). Then walk back (n-1,n-1) → (0,0) moving only left/up. Maximize cherries collected.

Reframing: Equivalent to TWO simultaneous walks from (0,0) → (n-1,n-1), each moving right/down. State (r1, c1, r2); derive c2 = r1 + c1 - r2 (both walks have made the same number of steps). If both at same cell, count cherry once.

O(n³) time / space.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/cherry-pickup/

STOP. 45-min timer. The “two simultaneous paths” reframing is the unlock.

3. Prerequisite Concepts

  • Grid DP (unique paths).
  • Why greedy “max path forward, max path back” fails (shown in 6.2).
  • State compression by invariant (c2 derived from r1+c1-r2).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Max cherries on a round trip; thorns block; eaten cherries don’t regrow.

2. Clarify: What if no valid path? Return 0. What if cells reused on round trip — eat twice? No (cherry consumed on first visit).

3. Examples: [[0,1,-1],[1,0,-1],[1,1,1]] → 5.

5. Brute: Enumerate all (forward, backward) path pairs. Exponential.

6. Target: O(n³).

7. Pattern: Multi-agent DP / dimension reduction by step-count invariant.

8. Develop: see solution.py.

9. Test: all zeros; thorn blocks all forward paths (return 0); single cell.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why the naive “forward greedy then backward greedy” fails

Take forward as “max cherry path to goal”, consume those cherries, then “max cherry path back”. This is suboptimal because the forward path’s greedy choice may starve the backward path of a much-better lane. Counterexample: a grid where two cherry-lanes exist; greedy forward takes one lane fully, leaving the backward to grab only the partial overlap.

6.2 The reframing: round trip = 2 simultaneous one-way trips

A “round trip A→B→A” where forward is right/down and backward is left/up is equivalent to two agents simultaneously walking A→B, both moving right/down. Why? Time-reverse the backward path → it becomes a right/down forward path. Cherries collected on the round trip = cherries collected by the union of two forward paths (with shared-cell deduplication).

6.3 State derivation: c2 = r1 + c1 - r2

Both agents move one step at a time (right or down). After step t, agent 1 is at (r1, c1) with r1+c1 = t; same for agent 2: r2+c2 = t. So c2 = r1 + c1 - r2. This drops the state from O(n⁴) to O(n³).

6.4 Shared-cell dedup

If (r1, c1) == (r2, c2) (same cell, same step), count the cherry once not twice. In code: gain = grid[r1][c1]; if (r1, c1) != (r2, c2): gain += grid[r2][c2].

6.5 Transitions: 4 combinations

Each agent moves down or right → 4 predecessor combos: (D,D), (D,R), (R,D), (R,R). Take max over predecessors that are valid (in-bounds and not thorns).

6.6 -inf for thorn cells / unreachable

If any cell on the path is -1, that state is invalid. Set dp[...] = -inf. Final answer: max(0, dp[n-1][n-1][n-1]).

6.7 Why this is “Cherry Pickup II” pattern foreshadowed

LC 1463 (Cherry Pickup II) has TWO robots starting at top corners, both walking down to bottom. Same multi-agent DP, slightly different state (r is shared since both move down 1 per step; state = (r, c1, c2)).

7. Anti-Pattern Analysis

  1. Greedy forward-then-backward — counterexample in 6.1.
  2. Treat as two independent shortest paths — ignores cherry consumption.
  3. State (r1, c1, r2, c2) (O(n⁴)) — works but wastes memory; misses the invariant.
  4. Forget the shared-cell dedup — over-counts cherries when paths cross.
  5. Forget max(0, ...) — return -inf when no valid path exists; must clamp to 0.
  6. Iterate t (step count) but forget r1+c1=t constraint — visits invalid states.

8. Skills & Takeaways

  • Multi-agent DP reframing.
  • Dimension reduction by invariant.
  • Round-trip = two one-way trips trick.

9. When to Move On

  • Solve cold in 40 min with O(n³).
  • Explain the “two simultaneous walks” reframing on the whiteboard.
  • Handle thorn invalidation cleanly.
  • Mention Cherry Pickup II as the K-agent generalization.

10. Company Context

  • Google: L5/L6; classic.
  • Amazon: L6; harder onsite.
  • Meta: E5/E6; rare but signals.

Strong: “Reframed as two simultaneous walks unprompted, derived c2 = r1+c1-r2 invariant, O(n³), correct shared-cell dedup, clean -inf propagation.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
ReframingNoneAfter hintCold+ K-agent generalization
StateO(n⁴)O(n³) after hintO(n³) cold+ cites Cherry Pickup II
DedupWrongAfter test failCold+ proves correctness rigorously
GeneralizationNoneNoneLC 1463+ multi-agent value iteration framing

12. Level Delta

  • Mid (L4): Brute or wrong-greedy; gets O(n⁴) DP after hints.
  • Senior (L5): Reframes cold, derives invariant, O(n³) with dedup.
  • Staff (L6): + cites Cherry Pickup II + frames as multi-agent value iteration.
  • Principal (L7+): + Bellman optimality on product MDP + K-agent extensions + connections to multi-commodity flow.

13. Follow-up Q&A

Q1: K agents instead of 2? A1: State (r1, c1, r2, c2, ..., rK, cK); can reduce one dim by step-count invariant; remaining O(n^(2K-1)). Exponential in K.

Q2: What if grid has weighted cherries (different values)? A2: Same DP; gain uses the weight not 1.

Q3: 4-directional movement instead of right/down only? A3: Loses DAG structure; becomes shortest-path with state including consumed cells → exponential. NP-hard in general.

Q4: Reconstruct the actual two paths? A4: Parent pointers per state; backtrack from (n-1,n-1,n-1).

Q5: Difference from Cherry Pickup II (LC 1463)? A5: Two robots both START at top (col 0 and col n-1) and both walk DOWN. State (r, c1, c2); both at same r per step.

14. Solution Walkthrough

See solution.py:

  • cherry_pickup_dp — top-down memoized 3D (r1, c1, r2).
  • cherry_pickup_iter — bottom-up 3D iterative by step count.
  • cherry_pickup_brute — enumerate all forward + backward path pairs (oracle for tiny grids).

15. Beyond the Problem

Principal code review: “Cherry Pickup is the prototype for ‘multi-agent grid DP with shared state’. The reframing — round trip becomes two simultaneous one-way trips — is the kind of move that distinguishes a senior IC from a staff engineer: instead of attacking the problem head-on, restructure the state space until the obstacles vanish. The same move appears in: multi-commodity flow (sending two flows is like sending one in a tensor-product graph), distributed systems consensus (n-replica problems reframed as 2-replica with witnesses), and ML (multi-task learning’s shared encoder = two tasks walking the same network). The general principle: ‘when two processes share structure, model them as one process on a product space.’ At Staff+, articulate this as Bellman optimality on a product MDP, then point out that the dimension reduction (c2 derived from r1+c1-r2) is just exploiting the conserved quantity (step count) — the same trick as exploiting conserved quantities in physics to reduce dimensionality of differential equations.”