HardArrayDynamic ProgrammingMatrix

Cherry Pickup

1 approach, code in every language

You are given an n x n grid. Each cell holds 0 (empty), 1 (one cherry), or -1 (a thorn that blocks the path). Starting at the top-left cell (0, 0), you walk to the bottom-right cell (n - 1, n - 1) moving only right or down, and then walk back to (0, 0) moving only left or up.

Along the way you collect every cherry you pass over, and once a cherry is picked the cell becomes empty. You may never step on a thorn. Return the maximum number of cherries you can collect over the round trip; if there is no valid path that reaches the bottom-right corner and returns, the answer is 0.

Example 1

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

Output: 5

One optimal round trip collects cherries on the way down through the left and bottom cells and picks up the remaining ones on the way back, gathering 5 in total while avoiding both thorns.

Example 2

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]

Output: 0

The thorns split the grid so that no path can reach the bottom-right corner, so no valid round trip exists and the answer is 0.

Constraints

n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] is -1, 0, or 1
grid[0][0] != -1 and grid[n - 1][n - 1] != -1

Two Simultaneous Walkers DP

Model the round trip as two people walking from the top-left at the same time, and DP over their synchronized positions.

Loading animation…

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

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).
2If any walker is off the board or on a thorn, mark the state as unreachable (negative infinity).
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.
4Advance one step and try the four move pairs: both down, first down and second right, first right and second down, or both right.
5Take the maximum reachable successor; if none is reachable the state itself is unreachable.
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

Time

O(n^3)

Space

O(n^3)

States are (steps, r1, r2) with O(n) values each and O(1) work per state; the third column is derived, so space can drop to O(n^2) with a rolling layer over steps.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Round Trip Parcel Pickup is our own problem on the technique behind Cherry Pickup: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free