LeetCode 741: Cherry Pickup

Problem Restatement

We are given an n x n grid.

Each cell contains one of three values:

We start at the top-left cell:

(0, 0)

We need to travel to the bottom-right cell:

(n - 1, n - 1)

using only:

right
down

Then we return from the bottom-right cell to the top-left cell using only:

left
up

Whenever we pass through a cell with a cherry, we collect it. After a cherry is collected, that cell becomes empty. A cherry can be collected at most once.

Return the maximum number of cherries we can collect. If there is no valid round trip, return 0.

The official constraints include 1 <= n <= 50, grid[i][j] is -1, 0, or 1, and the start and end cells are not thorns.

Input and Output

Example function shape:

def cherryPickup(grid: list[list[int]]) -> int:
    ...

Examples

Example 1

grid = [
    [0, 1, -1],
    [1, 0, -1],
    [1, 1,  1],
]

One optimal path goes down, down, right, right to reach the end.

Then the return path collects one remaining cherry.

The maximum total is:

5

So the answer is:

5

Example 2

grid = [
    [1, 1, -1],
    [1, -1, 1],
    [-1, 1, 1],
]

There is no valid way to complete the trip from start to end and back.

The answer is:

0

First Thought: Pick One Path, Then Pick Return Path

A tempting approach is:

1. Find a path from start to end that collects many cherries.
2. Remove those cherries.
3. Find the best return path.

This does not work.

The best first path may block the best total round trip. Sometimes we should collect fewer cherries on the way down so the return path can collect more.

So the two paths must be optimized together, not separately.

Key Insight

The return path from bottom-right to top-left using left and up can be reversed.

After reversing, it becomes another path from top-left to bottom-right using right and down.

So the whole round trip can be seen as:

two people start at (0, 0)
both move to (n - 1, n - 1)
each step is either right or down

Both people move at the same time.

If both people land on the same cell, we count its cherry once.

This converts the problem into a dynamic programming problem over two simultaneous paths. This is the standard formulation for this problem.

Algorithm

Let:

dp[k][r1][r2]

mean the maximum cherries collected after both people have taken exactly k steps.

At step k:

person 1 is at (r1, c1)
person 2 is at (r2, c2)

Since each person has taken k total moves:

c1 = k - r1
c2 = k - r2

So we only need k, r1, and r2.

For each state:

1. Skip it if either position is outside the grid.
2. Skip it if either position is a thorn.
3. Try the four possible previous states:
   • both came from above
   • person 1 from above, person 2 from left
   • person 1 from left, person 2 from above
   • both came from left
4. Add cherries from the current cells.
5. If both people are on the same cell, add the cherry once.

The answer is:

max(0, dp[2 * n - 2][n - 1][n - 1])

We use max(0, ...) because unreachable states are stored as negative infinity.

Correctness

Reversing the return trip transforms it into a second forward trip from (0, 0) to (n - 1, n - 1). Therefore every valid round trip corresponds to two simultaneous forward paths, and every pair of forward paths corresponds to one round trip.

At step k, both paths have made the same number of moves. If one path is at row r, its column is forced to be k - r. Therefore the state dp[k][r1][r2] fully describes both positions.

The transition checks all possible previous moves for both paths. Since each person can only move right or down, their previous cell must have been either above or left. The four previous-state combinations cover all valid ways to arrive at the current pair of cells.

The value added at each state is exactly the number of new cherries collected at the two current positions. If the two people stand on different cells, both cherries may be counted. If they stand on the same cell, the cherry is counted once, matching the rule that each cherry can be collected only once.

The DP processes steps in increasing order, so every previous state is already computed before it is used.

Thus the final state gives the maximum cherries over all valid pairs of paths. If the final state is unreachable, the correct answer is 0.

Complexity

Let n be the grid size.

This can be optimized to O(n^2) space by keeping only the previous step, but the full DP version is easier to read.

Implementation

class Solution:
    def cherryPickup(self, grid: list[list[int]]) -> int:
        n = len(grid)
        neg_inf = float("-inf")

        steps = 2 * n - 1
        dp = [
            [[neg_inf] * n for _ in range(n)]
            for _ in range(steps)
        ]

        dp[0][0][0] = grid[0][0]

        for k in range(1, steps):
            for r1 in range(n):
                for r2 in range(n):
                    c1 = k - r1
                    c2 = k - r2

                    if c1 < 0 or c1 >= n:
                        continue

                    if c2 < 0 or c2 >= n:
                        continue

                    if grid[r1][c1] == -1:
                        continue

                    if grid[r2][c2] == -1:
                        continue

                    best_prev = neg_inf

                    for prev_r1 in (r1, r1 - 1):
                        for prev_r2 in (r2, r2 - 1):
                            if prev_r1 < 0 or prev_r2 < 0:
                                continue

                            best_prev = max(
                                best_prev,
                                dp[k - 1][prev_r1][prev_r2],
                            )

                    if best_prev == neg_inf:
                        continue

                    cherries = grid[r1][c1]

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

                    dp[k][r1][r2] = best_prev + cherries

        return max(0, dp[steps - 1][n - 1][n - 1])

Code Explanation

We use neg_inf for impossible states:

neg_inf = float("-inf")

The number of simultaneous steps from (0, 0) to (n - 1, n - 1) is:

steps = 2 * n - 1

That includes step 0.

The start state is:

dp[0][0][0] = grid[0][0]

At each step, columns are derived from rows:

c1 = k - r1
c2 = k - r2

If either column is outside the grid, the state is impossible.

If either cell is a thorn, the state is impossible:

if grid[r1][c1] == -1:
    continue

if grid[r2][c2] == -1:
    continue

For each current row, the previous row was either the same row or one row above:

for prev_r1 in (r1, r1 - 1):
    for prev_r2 in (r2, r2 - 1):

Same row means the person came from the left.

One row above means the person came from above.

Then we count cherries:

cherries = grid[r1][c1]

If the two people are on different cells, add both cells:

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

Finally, return the best valid result, or 0 if no valid path exists.

Testing

def run_tests():
    s = Solution()

    assert s.cherryPickup([
        [0, 1, -1],
        [1, 0, -1],
        [1, 1,  1],
    ]) == 5

    assert s.cherryPickup([
        [1, 1, -1],
        [1, -1, 1],
        [-1, 1, 1],
    ]) == 0

    assert s.cherryPickup([[0]]) == 0
    assert s.cherryPickup([[1]]) == 1

    assert s.cherryPickup([
        [1, 1],
        [1, 1],
    ]) == 4

    assert s.cherryPickup([
        [0, 1, 1],
        [1, -1, 1],
        [1, 1, 1],
    ]) == 7

    print("all tests passed")

run_tests()