Get started

Cherry Pickup — Hard Problem & Solution

An n × n grid holds 0 (empty), 1 (a cherry) or -1 (a thorn you cannot enter).

Problem statement

An n × n grid holds 0 (empty), 1 (a cherry) or -1 (a thorn you cannot enter).

Walk from (0,0) to (n-1,n-1) moving only right or down, then walk back to (0,0) moving only left or up, picking up every cherry you pass (each cell's cherry is taken at most once). Return the maximum cherries collected, or 0 if the round trip is impossible.

Example 1

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: One path down the left and back along the bottom collects five cherries.

Example 2

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0
Explanation: No round trip exists.

Example 3

Input: grid = [[1,1],[1,1]]
Output: 4

Constraints

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

How to solve Cherry Pickup

Reverse the return journey into a second outbound journey, then advance both walkers in lockstep. After t steps each sits on the diagonal row + col = t, so the state is (t, row1, row2) and the column follows.

Approach

  1. dp[r1][r2] is the best total after t steps with the walkers on rows r1 and r2.
  2. Advance t; each walker either kept its row (moved right) or came from the row above (moved down) — four combinations.
  3. Add grid[r1][c1], plus grid[r2][c2] only when the walkers are on different rows, so a shared cell is counted once.
  4. Skip any state landing on a thorn; the answer is max(0, dp[n-1][n-1]) at the final step.

Why it works

Two independent one-way trips collect exactly what one round trip does, because reversing a path preserves the cells visited. The lockstep is what makes the 'shared cell' rule checkable: two walkers can only meet when they are on the same diagonal at the same time, which is precisely when r1 == r2. Clamping the final answer at 0 handles the case where no valid round trip exists, which the NEG sentinel propagates.

Complexity

  • Time — O(n³)
  • Space — O(n²)

Pitfalls

  • Running two independent greedy or DP passes is wrong — the best single path twice may overlap badly.
  • Forgetting the r1 == r2 check double-counts a cherry.
  • Unreachable states must stay at the sentinel and not leak into a maximum.

Reference solution

Python

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    NEG = -10 ** 6
    dp = [[NEG] * n for _ in range(n)]
    dp[0][0] = grid[0][0]
    for t in range(1, 2 * (n - 1) + 1):
        ndp = [[NEG] * n for _ in range(n)]
        lo, hi = max(0, t - (n - 1)), min(n - 1, t)
        for r1 in range(lo, hi + 1):
            for r2 in range(lo, hi + 1):
                c1, c2 = t - r1, t - r2
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                best = NEG
                for p1 in (r1 - 1, r1):
                    for p2 in (r2 - 1, r2):
                        if p1 < 0 or p2 < 0:
                            continue
                        best = max(best, dp[p1][p2])
                if best == NEG:
                    continue
                val = grid[r1][c1]
                if r1 != r2:
                    val += grid[r2][c2]
                ndp[r1][r2] = best + val
        dp = ndp
    return max(0, dp[n - 1][n - 1])

JavaScript

var cherryPickup = function(grid) {
    var NEG = -1000000;
    var n = grid.length;
    var mk = function() {
        var m = [];
        for (var a = 0; a < n; a++) {
            var row = [];
            for (var b = 0; b < n; b++) row.push(NEG);
            m.push(row);
        }
        return m;
    };
    var dp = mk();
    dp[0][0] = grid[0][0];
    for (var t = 1; t <= 2 * (n - 1); t++) {
        var ndp = mk();
        var lo = Math.max(0, t - (n - 1)), hi = Math.min(n - 1, t);
        for (var r1 = lo; r1 <= hi; r1++) {
            for (var r2 = lo; r2 <= hi; r2++) {
                var c1 = t - r1, c2 = t - r2;
                if (grid[r1][c1] === -1 || grid[r2][c2] === -1) continue;
                var best = NEG;
                var p1s = [r1 - 1, r1], p2s = [r2 - 1, r2];
                for (var a = 0; a < 2; a++) {
                    for (var b = 0; b < 2; b++) {
                        var p1 = p1s[a], p2 = p2s[b];
                        if (p1 < 0 || p2 < 0) continue;
                        if (dp[p1][p2] > best) best = dp[p1][p2];
                    }
                }
                if (best === NEG) continue;
                var val = grid[r1][c1];
                if (r1 !== r2) val += grid[r2][c2];
                ndp[r1][r2] = best + val;
            }
        }
        dp = ndp;
    }
    return Math.max(0, dp[n - 1][n - 1]);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue