Cherry Pickup: Two-Path DP on a Grid

You have a grid full of cherries, and you want to collect as many as possible on a round trip from the top-left corner to the bottom-right and back. Sounds simple enough, right? Just find the best path forward, then the best path back. But that greedy approach fails badly. The first trip can leave the grid in a state where the return trip collects far fewer cherries than a globally optimal pair of paths would. This is LeetCode 741: Cherry Pickup, and the trick is to reframe the entire problem as two people walking forward at the same time.

The problem

You are given an n x n grid where each cell contains one of three values: 0 (empty), 1 (cherry), or -1 (thorn that blocks the path). Starting at (0, 0), you need to reach (n-1, n-1) moving only right or down, collecting cherries along the way. Then you return from (n-1, n-1) to (0, 0) moving only left or up, collecting more cherries. Each cherry can only be collected once. If no valid round trip exists, return 0. Find the maximum number of cherries you can collect.

The naive "go then return" strategy fails because picking cherries on the first trip changes the grid for the second trip. A locally optimal first path might block the globally optimal combination of two paths. You need to consider both trips together.

The approach

The key insight is that a return trip from (n-1, n-1) to (0, 0) using left and up moves is just a forward trip from (0, 0) to (n-1, n-1) using right and down moves, traversed in reverse. So the round trip is equivalent to sending two walkers simultaneously from (0, 0) to (n-1, n-1), both moving only right or down.

At each step t, both walkers have made exactly t moves total. Walker 1 is at row r1 (so column c1 = t - r1), and walker 2 is at row r2 (so column c2 = t - r2). Since t = r1 + c1 = r2 + c2, we can derive c2 from the other three variables. This collapses the state from four dimensions (r1, c1, r2, c2) down to three: (r1, c1, r2).

At each state, we collect the cherries in both cells. If both walkers happen to be on the same cell, we count that cherry only once. Then we try all four combinations of moves (each walker goes down or right) and take the maximum.

def cherry_pickup(grid: list[list[int]]) -> int:
    n = len(grid)
    memo = {}

    def dp(r1, c1, r2):
        c2 = r1 + c1 - r2
        if r1 >= n or c1 >= n or r2 >= n or c2 >= n:
            return float('-inf')
        if grid[r1][c1] == -1 or grid[r2][c2] == -1:
            return float('-inf')
        if r1 == n - 1 and c1 == n - 1:
            return grid[r1][c1]
        if (r1, c1, r2) in memo:
            return memo[(r1, c1, r2)]

        cherries = grid[r1][c1]
        if r1 != r2 or c1 != c2:
            cherries += grid[r2][c2]

        best = max(
            dp(r1 + 1, c1, r2 + 1),
            dp(r1 + 1, c1, r2),
            dp(r1, c1 + 1, r2 + 1),
            dp(r1, c1 + 1, r2),
        )
        cherries += best
        memo[(r1, c1, r2)] = cherries
        return cherries

    return max(0, dp(0, 0, 0))

Step-by-step walkthrough

Let's walk through how the DP works on the example grid [[0,1,-1],[1,0,1],[1,1,0]]. Both walkers start at (0, 0) and need to reach (2, 2), collecting as many cherries as possible between them.

The optimal split has walker 1 taking the left-bottom path through (1,0), (2,0), (2,1) and walker 2 taking the top-right path through (0,1), (1,2). Together they collect all 5 cherries, with no overlap. If you had tried a single greedy forward path first, you might have collected 3 cherries going forward and then found only 1 or 2 on the way back, missing the global optimum.

Complexity analysis

Time: The state space has three dimensions, each ranging from 0 to n - 1. That gives O(n^3) unique states. Each state does O(1) work (checking four transitions and taking the max). So total time is O(n^3).

Space: The memoization table stores one entry per state, so it uses O(n^3) space. The recursion stack can go up to O(n) deep, but that is dominated by the memo table.

The building blocks

Two-walker simulation

The core technique here is converting a "go and return" problem into a "two walkers going forward" problem. This works because a return path (moving left and up) is just a forward path (moving right and down) traversed in reverse. By sending two walkers simultaneously, you can reason about both paths in a single DP without needing to modify the grid between trips.

The two-walker framing also makes the "collect once" constraint easy to handle. When both walkers occupy the same cell at the same step, you simply count that cell's cherry once instead of twice. Without this framing, you would need to track which cells have already been picked on the first trip, which would explode the state space.

This pattern generalizes to any problem where you need to find two optimal paths through a grid simultaneously. The step-based parameterization (t = r + c) is what makes the state reduction from 4D to 3D possible. Any time two agents move in lockstep through a grid with shared resources, consider this approach.

Edge cases

• No valid path: if thorns block every route from (0, 0) to (n-1, n-1), the DP returns negative infinity for all paths. The max(0, ...) at the end ensures you return 0 rather than a negative number.
• Single cell (1x1): the grid is just [[v]]. Both walkers start and end at the same cell, so the answer is max(0, v). If it is a thorn (-1), return 0.
• No cherries: every cell is 0. Both walkers can reach the destination, but there is nothing to collect. The answer is 0.
• Both walkers on the same path: when the grid is narrow or the optimal strategy has both walkers taking identical routes, the DP naturally handles this by counting shared cells only once. You do not need a special case.

From understanding to recall

You now understand why the go-and-return approach fails, how the two-walker reframing works, and how step-based indexing reduces the state space from 4D to 3D. But reproducing this under interview pressure is a different skill.

The pattern to internalize is: whenever a problem involves two traversals of the same grid with shared resources, convert it into two simultaneous forward traversals. Then define your DP state using the step count and each walker's row, deriving columns from the constraint t = r + c. Practice writing the recurrence from memory a few times, and the structure becomes automatic.

Spaced repetition is the fastest way to lock this in. Revisit this problem at increasing intervals, each time writing the two-walker DP setup without looking at the solution. After a few reps, the "two walkers, three-dimensional state" pattern will fire instantly when you see a round-trip grid problem.

Related posts

• Minimum Path Sum - The simpler single-path grid DP this builds on
• Unique Paths - Counting paths in a grid, the foundation for grid DP
• Dungeon Game - Another grid DP with constraints on path validity