Cherry Pickup

Cherry Pickup is a hard DP problem with a beautiful trick: a single trip down with two walkers at once beats reasoning about two separate trips. It teaches how to collapse a coupled pair of paths into one state and how to avoid double-counting where they meet.

The slow way first

The tempting idea is to find the single best path, take its cherries away, then find the best path on what is left. This greedy two-pass approach is wrong: the best first path can starve the second one. The two paths must be chosen together, weighing how they share cells.

Choosing two independent full paths is exponential. The question to ask: what is the smallest piece of state that describes both walkers at one moment?

The idea: two walkers descending in lockstep

Send both walkers down at the same time, one row per step. Because they always move down exactly once per step, after r steps both sit on row r. So the entire situation is captured by (r, c1, c2) — the row, and each walker's column. The second column is not free; it is just the other walker's position on that same row.

The key subtlety: when c1 == c2 both walkers stand on the same cell, so its cherry is counted once, not twice. That single guard is the whole difference between a correct solution and double-counting.

Walk through it

Step through the animation. Walker A starts top-left, walker B top-right, both on row 0. Each step they descend together. While their columns differ, each contributes its own cell's cherry. Watch the final row: both land on the same cell, so the cherry there is added once.

Pseudocode

best(r, c1, c2):
    if either column is off the grid or on a thorn: return -infinity
    cur = grid[r][c1]
    if c1 != c2: cur += grid[r][c2]        # same cell counts once
    if r is the last row: return cur
    nxt = max over dc1, dc2 in {-1, 0, +1}:
              best(r + 1, c1 + dc1, c2 + dc2)
    return cur + nxt
answer = max(0, best(0, 0, n - 1))         # A top-left, B top-right

The Python solution

def cherry_pickup(grid):
    n = len(grid)
    from functools import lru_cache
    @lru_cache(None)
    def best(r, c1, c2):
        if c1 < 0 or c1 >= n or c2 < 0 or c2 >= n:
            return float('-inf')
        if grid[r][c1] == -1 or grid[r][c2] == -1:
            return float('-inf')
        cur = grid[r][c1]
        if c1 != c2:
            cur += grid[r][c2]
        if r == n - 1:
            return cur
        nxt = max(best(r + 1, c1 + dc1, c2 + dc2)
                  for dc1 in (-1, 0, 1) for dc2 in (-1, 0, 1))
        return cur + nxt
    return max(0, best(0, 0, n - 1))

• best(r, c1, c2) is the most cherries both walkers can still gather from row r downward, given their columns.
• The first guard rejects any move that leaves the grid or lands on a -1 thorn by returning -inf, so it never wins a max.
• cur = grid[r][c1] takes A's cherry; line 11 adds B's cherry only when c1 != c2 — the shared-cell guard.
• At the last row we just return cur; otherwise lines 15-16 try all nine next-column pairs and keep the best.
• @lru_cache memoizes on (r, c1, c2), turning the exponential recursion into polynomial work. The final max(0, ...) guards the case where no valid path exists.

Complexity

The win comes from realizing the two paths move in lockstep, which fuses two O(n²)-position walkers into one O(n³) state space instead of an exponential search over independent paths.

When this pattern shows up

Practice