Cherry Pickup

Hard Dynamic Programming 2D DP Original on LeetCode

Reported atFlipkartInMobi

Cherry Pickup is a hard dynamic programming problem solved with the 2d dp pattern. The best approach, optimal (bottom-up dp over diagonals), runs in O(n³) time and O(n²) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (move two walkers recursively) up.

Problem

You are given an n x n field grid where each cell is 1 (a cherry), 0 (empty) or -1 (a thorn bush you cannot walk through).

Start at the top-left cell (0, 0), walk to the bottom-right cell (n - 1, n - 1) moving only right or down, then walk back to (0, 0) moving only left or up. Every cherry you step on is picked, and its cell becomes empty, so a cherry visited twice is collected once.

Return the largest number of cherries you can collect. If there is no valid route from (0, 0) to (n - 1, n - 1), return 0.

Examples

Example 1

Input
grid = [[0, 1, 1], [1, -1, 1], [1, 1, 0]]
Output
6
Why
Go down the left column and along the bottom row (3 cherries), then come back up the right column and along the top row (3 more).

Example 2

Input
grid = [[1, 1, -1], [-1, 1, 1], [1, -1, 1]]
Output
5
Why
Only one route avoids the thorns: right, down, right, down. It holds 5 cherries, and the walk back over the same cells finds nothing new.

Example 3

Input
grid = [[0, -1], [-1, 0]]
Output
0
Why
Both cells next to the start are thorns, so the far corner cannot be reached and the answer is 0.

Constraints

  • n == grid.length == 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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (move two walkers recursively)O(4^(2n))O(n)
Better (memoized recursion)O(n³)O(n³)
Optimal (bottom-up DP over diagonals)O(n³)O(n²)

1Brute force (move two walkers recursively)

TimeO(4^(2n))Each of the 2n - 2 steps branches into four calls.
SpaceO(n)The recursion is 2n - 1 calls deep.

Replace the round trip by two walkers that both start at (0, 0) and move down or right in lockstep. After the same number of steps, walker 2's column is fixed by c2 = r1 + c1 - r2. Try all four combinations of moves at each step and keep the best total, counting a shared cell once.

  1. go(r1, c1, r2): compute c2; if any coordinate leaves the grid or either cell is a thorn, return a large negative value.
  2. Collect grid[r1][c1], plus grid[r2][c2] if the walkers are on different cells.
  3. If walker 1 reached (n - 1, n - 1), return that amount (walker 2 is there too).
  4. Otherwise add the best of the four next moves; a negative best means no way forward.
  5. The answer is max(0, go(0, 0, 0)).
class Solution {
    private static final int NEG = -1_000_000;

    public int cherryPickup(int[][] grid) {
        return Math.max(0, go(grid, 0, 0, 0));
    }

    private int go(int[][] g, int r1, int c1, int r2) {
        int n = g.length;
        int c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n) return NEG;
        if (g[r1][c1] == -1 || g[r2][c2] == -1) return NEG;
        int here = g[r1][c1];
        if (r1 != r2) here += g[r2][c2];
        if (r1 == n - 1 && c1 == n - 1) return here;
        int best = Math.max(
            Math.max(go(g, r1 + 1, c1, r2 + 1), go(g, r1 + 1, c1, r2)),
            Math.max(go(g, r1, c1 + 1, r2 + 1), go(g, r1, c1 + 1, r2)));
        return best < 0 ? NEG : here + best;
    }
}

2Better (memoized recursion)

TimeO(n³)n³ states, each doing constant work besides its four lookups.
SpaceO(n³)The memo table has n³ entries.

The brute force recomputes the same (r1, c1, r2) states over and over. There are only n³ of them, so cache each result the first time it is computed.

  1. Keep a 3D memo indexed by (r1, c1, r2), initially marked as not computed.
  2. Run the same recursion as before, but return the cached value when present and store every new result.
  3. Return max(0, go(0, 0, 0)).
class Solution {
    private static final int NEG = -1_000_000;
    private static final int UNSET = Integer.MIN_VALUE;
    private int[][][] memo;

    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        memo = new int[n][n][n];
        for (int[][] plane : memo) {
            for (int[] row : plane) Arrays.fill(row, UNSET);
        }
        return Math.max(0, go(grid, 0, 0, 0));
    }

    private int go(int[][] g, int r1, int c1, int r2) {
        int n = g.length;
        int c2 = r1 + c1 - r2;
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n) return NEG;
        if (g[r1][c1] == -1 || g[r2][c2] == -1) return NEG;
        if (memo[r1][c1][r2] != UNSET) return memo[r1][c1][r2];
        int here = g[r1][c1];
        if (r1 != r2) here += g[r2][c2];
        int result;
        if (r1 == n - 1 && c1 == n - 1) {
            result = here;
        } else {
            int best = Math.max(
                Math.max(go(g, r1 + 1, c1, r2 + 1), go(g, r1 + 1, c1, r2)),
                Math.max(go(g, r1, c1 + 1, r2 + 1), go(g, r1, c1 + 1, r2)));
            result = best < 0 ? NEG : here + best;
        }
        memo[r1][c1][r2] = result;
        return result;
    }
}

3Optimal (bottom-up DP over diagonals)

TimeO(n³)2n - 1 steps, each filling at most n x n states with constant work.
SpaceO(n²)Two n x n tables: the previous step and the current one.

Process the walkers step by step. After t steps walker k is at (rk, t - rk), so dp[r1][r2] for the current t describes both positions. Each state is reached from the previous step's dp[r1][r2], dp[r1 - 1][r2], dp[r1][r2 - 1] or dp[r1 - 1][r2 - 1]. Only the previous step is needed, so two n x n tables suffice.

  1. Fill dp with NEG and set dp[0][0] = grid[0][0].
  2. For t = 1 to 2n - 2, create a new table; for every valid r1, r2 (row in range and column t - r in range) where neither cell is a thorn, take the best of the four previous states.
  3. If that best is non-negative, store best + cherries at both cells (once if r1 == r2).
  4. After the last step, return max(0, dp[n - 1][n - 1]).
class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        final int NEG = -1_000_000;
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, NEG);
        dp[0][0] = grid[0][0];
        for (int t = 1; t <= 2 * n - 2; t++) {
            int[][] next = new int[n][n];
            for (int[] row : next) Arrays.fill(row, NEG);
            int lo = Math.max(0, t - (n - 1)), hi = Math.min(n - 1, t);
            for (int r1 = lo; r1 <= hi; r1++) {
                int c1 = t - r1;
                if (grid[r1][c1] == -1) continue;
                for (int r2 = lo; r2 <= hi; r2++) {
                    int c2 = t - r2;
                    if (grid[r2][c2] == -1) continue;
                    int best = dp[r1][r2];
                    if (r1 > 0) best = Math.max(best, dp[r1 - 1][r2]);
                    if (r2 > 0) best = Math.max(best, dp[r1][r2 - 1]);
                    if (r1 > 0 && r2 > 0) best = Math.max(best, dp[r1 - 1][r2 - 1]);
                    if (best < 0) continue;
                    int gain = grid[r1][c1];
                    if (r1 != r2) gain += grid[r2][c2];
                    next[r1][r2] = best + gain;
                }
            }
            dp = next;
        }
        return Math.max(0, dp[n - 1][n - 1]);
    }
}

Edge cases to test

  • A 1 x 1 grid: the answer is the single cell's value
  • The bottom-right corner is unreachable: the answer is 0, not a negative number
  • Taking the single best path first and then the best remaining path is NOT optimal
  • Both trips passing through the same cell must count its cherry only once

Hints

Hint 1

The return trip is just another path from the top-left to the bottom-right, walked backwards. So think of two people walking down-right at the same time.

Hint 2

After t steps both walkers are on the anti-diagonal r + c = t. The state (t, r1, r2) is enough to know both positions.

Hint 3

If both walkers land on the same cell, add its cherry once. Each state comes from four previous states (each walker moved down or right).

FAQ

What is the best time complexity for Cherry Pickup?

Optimal (bottom-up DP over diagonals) runs in O(n³) time and O(n²) extra space. 2n - 1 steps, each filling at most n x n states with constant work.

Which pattern does Cherry Pickup use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.

Is there a brute force solution for Cherry Pickup?

Yes. Brute force (move two walkers recursively) takes O(4^(2n)) time and O(n) space. Replace the round trip by two walkers that both start at (0, 0) and move down or right in lockstep.

Which edge cases should I test for Cherry Pickup?

A 1 x 1 grid: the answer is the single cell's value; The bottom-right corner is unreachable: the answer is 0, not a negative number; Taking the single best path first and then the best remaining path is NOT optimal; Both trips passing through the same cell must count its cherry only once.