Cherry Pickup II

Cherry Pickup II takes the familiar grid-DP and adds a twist: two robots walk the grid at the same time, and their choices interact. The trick is to track both robots in one state and let the DP explore every legal pair of moves at once.

3 1 1 0
2 5 0 0
0 0 3 1

The slow way first

You might try to find robot 1 best path, then robot 2 best path. That fails: the two paths compete for the same cherries, so greedily optimizing one ruins the other. You also cannot brute-force every pair of full paths — there are exponentially many.

The question to ask: what is the smallest piece of state that fully describes where both robots are? Since they always move down together, both are on the same row r. So the only freedom is their two columns, c1 and c2. That is the whole state.

The idea: one DP over both robots

Define dp(r, c1, c2) = the most cherries collectable from row r onward, given robot 1 in column c1 and robot 2 in column c2. At each cell we collect grid[r][c1], and grid[r][c2] only if c1 != c2 (otherwise we would double-count the shared cell). Then each robot independently steps to one of three columns, giving 9 combinations for the next row — we take the best legal one.

The key insight: keeping both robots in a single state is what lets the DP weigh their competition correctly, and the c1 != c2 guard is what stops a shared cell from being counted twice.

Walk through it

Step through the animation. R1 (blue) starts top-left, R2 (orange) top-right. Each row both robots drop down and we add the cherries they land on. Watch the running total: 3 in row 0, +5 in row 1, +4 in row 2, reaching 12. At every row the engine quietly tried all 9 move pairs and kept the best.

Pseudocode

dp(r, c1, c2):
    cherries = grid[r][c1]
    if c1 != c2:                 # different cells -> add the second too
        cherries += grid[r][c2]
    if r is the last row:
        return cherries
    best = 0
    for each move d1 in (-1, 0, 1):
        for each move d2 in (-1, 0, 1):
            n1, n2 = c1 + d1, c2 + d2
            if both n1 and n2 are inside the grid:
                best = max(best, dp(r + 1, n1, n2))
    return cherries + best
 
answer = dp(0, 0, cols - 1)

The Python solution

def cherry_pickup(grid):
    rows, cols = len(grid), len(grid[0])
    from functools import lru_cache
    @lru_cache(None)
    def dp(r, c1, c2):
        cherries = grid[r][c1]
        if c1 != c2:
            cherries += grid[r][c2]
        if r == rows - 1:
            return cherries
        best = 0
        for d1 in (-1, 0, 1):
            for d2 in (-1, 0, 1):
                n1, n2 = c1 + d1, c2 + d2
                if 0 <= n1 < cols and 0 <= n2 < cols:
                    best = max(best, dp(r + 1, n1, n2))
        return cherries + best
    return dp(0, 0, cols - 1)

• dp(r, c1, c2) is memoized with lru_cache, so each (r, c1, c2) state is solved once.
• We always add grid[r][c1]; the if c1 != c2 guard adds the second robot cell only when they differ — this is the double-count fix.
• The base case r == rows - 1 returns just this row cherries (no more moves below).
• The double loop over d1, d2 enumerates all 9 next-row column pairs; the bounds check keeps both robots inside the grid.
• The answer is dp(0, 0, cols - 1) — both robots at their starting corners on row 0.

Complexity

The cache holds one entry per (r, c1, c2) state, and each state does a constant amount of work, so the whole solution is polynomial despite the exponential number of raw path pairs.

When this pattern shows up

Practice