Cherry Pickup

Intuition

A round trip down and back is equivalent to sending two people from the top-left to the bottom-right at the same time, both moving only right or down; the second traveler's forward path represents the return trip reversed. Because both take exactly one step per turn, after s steps each is on a cell whose row and column sum to s, so a person's position is fully described by its row once we fix the step count. This shrinks the state to (steps, r1, r2), with the columns recovered as c1 = steps - r1 and c2 = steps - r2. At each state we add the cherry at each walker's cell, but if both walkers share the same cell we must count that cherry only once. Taking the best over the four combinations of each walker moving right or down, and rejecting thorns and off-board cells, yields the optimum; an unreachable configuration is treated as negative infinity.

Algorithm walkthrough

1. 1Interpret the trip as two walkers starting together at (0, 0), each taking steps moves; walker positions are (r1, steps - r1) and (r2, steps - r2).
2. 2If any walker is off the board or on a thorn, mark the state as unreachable (negative infinity).
3. 3Collect grid[r1][c1], and add grid[r2][c2] only when the two walkers are on different cells so a shared cherry is not double-counted.
4. 4Advance one step and try the four move pairs: both down, first down and second right, first right and second down, or both right.
5. 5Take the maximum reachable successor; if none is reachable the state itself is unreachable.
6. 6Start from (steps = 0, r1 = 0, r2 = 0) and return max(0, result) so an impossible trip yields zero.

Implementation

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        NEG = float('-inf')
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(steps: int, r1: int, r2: int) -> float:
            c1 = steps - r1
            c2 = steps - r2
            if (r1 < 0 or r1 >= n or r2 < 0 or r2 >= n or
                    c1 < 0 or c1 >= n or c2 < 0 or c2 >= n or
                    grid[r1][c1] == -1 or grid[r2][c2] == -1):
                return NEG
            if r1 == n - 1 and c1 == n - 1:
                return grid[r1][c1]
            cherries = grid[r1][c1]
            if r1 != r2:
                cherries += grid[r2][c2]
            best = max(
                dp(steps + 1, r1 + 1, r2 + 1),
                dp(steps + 1, r1 + 1, r2),
                dp(steps + 1, r1, r2 + 1),
                dp(steps + 1, r1, r2),
            )
            if best == NEG:
                return NEG
            return cherries + best

        result = dp(0, 0, 0)
        return max(0, int(result)) if result != NEG else 0