Cherry Pickup

Hard25–30 min

Topics

Dynamic ProgrammingMatrix

Companies

GoogleAmazon

Given a square grid where each cell is blocked, empty, or holds one cherry, imagine making two trips from the top-left corner to the bottom-right corner, each only moving right or down. Find the maximum total number of cherries collectible across both trips combined — a cell visited by both trips only counts once — or 0 if no such pair of trips is possible at all. Since both trips always take the same number of steps to have moved the same distance, their positions at any point can be tracked by row alone (the column follows from the step count), which keeps the state small enough to work with directly: track, after each step, the best total collectible so far for every pair of rows the two trips could be on. Starting both trips together at the top-left corner and sweeping forward one step at a time — where each trip independently either moves down or moves right — lets every later step be resolved using totals already computed for the step before it, skipping any pair of positions that would land on a blocked cell. Once both trips reach the bottom-right corner, that entry holds the answer.

Test Case 1:

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

Output:8

Explanation:Two trips from the top-left to the bottom-right corner, each only moving right or down, collect a combined 8 cherries while routing around the blocked center cell — a shared cell counts once.

Test Case 2:

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

Output:2

Explanation:With only one possible pair of routes, both trips collect the corner cells: 1 + 1 = 2.

Test Case 3:

Input:grid = [[1]]

Output:1

Explanation:A single cell is both the start and the end — it's collected once, not twice.

Constraints

◆1 ≤ grid.length ≤ 15 (a square n×n grid)
◆grid[i][j] is -1 (blocked), 0 (empty), or 1 (one cherry)
◆grid[0][0] and grid[n-1][n-1] are never -1

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Think of it as two trips made at the same time, both starting at the top-left corner and both only moving right or down, each step taken simultaneously so both trips are always the same number of steps in. At every step, each trip independently moves right or down, giving up to four combined moves, and a move into a blocked cell — or off the grid — simply isn't allowed. Whenever both trips are on the same cell, its cherry is only collected once. From any pair of positions, the most cherries collectible from there onward is this step's cherries (for one or both trips) plus whichever of the reachable next pairs of positions collects the most; once both trips reach the bottom-right corner, there's nothing left to collect but that cell itself. Trying every combination of moves finds the maximum, though the same pair of positions ends up recomputed whenever different routes funnel into it, and the whole result is floored at 0 in case no route through survives at all.

TimeO(4^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[][] grid;
    private int n;

    public int cherryPickup(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
        int result = solve(0, 0, 0);
        return Math.max(result, 0);
    }

    private int solve(int r1, int c1, int r2) {
        int c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return Integer.MIN_VALUE;
        }
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }
        int best = Integer.MIN_VALUE;
        best = Math.max(best, solve(r1 + 1, c1, r2 + 1));
        best = Math.max(best, solve(r1 + 1, c1, r2));
        best = Math.max(best, solve(r1, c1 + 1, r2 + 1));
        best = Math.max(best, solve(r1, c1 + 1, r2));
        if (best == Integer.MIN_VALUE) return Integer.MIN_VALUE;
        int cherries = grid[r1][c1];
        if (r1 != r2) cherries += grid[r2][c2];
        return cherries + best;
    }
}

Optimal — Bottom-Up 2D Table Per Step

Optimal

Since both trips always take the same number of steps to reach any given pair of rows, a trip's column is fixed once its row and the step count are known (column = step − row). That means the state only needs each trip's row, so track a table indexed by "trip 1's row" and "trip 2's row" holding the most cherries collectible so far after a given number of steps. Step 0 starts both trips together at the top-left corner. At every step after that, each new entry is this step's cherries (for the pair of cells, counted once if they coincide) plus the best entry reachable from the previous step across the up to four combined moves — each trip either stayed in the same row (moved right) or advanced a row (moved down) — skipping any move into a blocked cell or off the grid. After the final step, when both trips have reached the bottom-right corner, that entry holds the answer, floored at 0.

TimeO(n³)

SpaceO(n²)