Cherry Pickup II — Hard Problem & Solution

Two robots collect cherries from a grid. Robot 1 starts at (0, 0) and robot 2 at (0, n-1).

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Matrix
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two robots collect cherries from a grid. Robot 1 starts at (0, 0) and robot 2 at (0, n-1). From a cell (i, j) a robot moves to (i+1, j-1), (i+1, j) or (i+1, j+1), and both move one row per turn until they reach the bottom row.

A robot collects the cherries in every cell it visits, and a cell is emptied once visited. If both robots land on the same cell, the cherries there are collected only once.

Return the maximum total cherries.

Example 1

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Robot 1 takes the left path and robot 2 the right; they never share a cell.

Example 2

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28

Example 3

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

Constraints

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

How to solve Cherry Pickup II

Because the robots descend in lockstep, the row is common to both and the state is just the pair of columns. dp[c1][c2] is the best total with the robots at those columns on the current row; each step tries all nine column moves.

Approach

Initialise dp[0][n-1] with the first row's two starting cells (once if n == 1).
For each subsequent row, build next by trying d1, d2 each in {-1, 0, 1}.
The gain is grid[row][n1] + grid[row][n2], or just one of them when n1 == n2.
After the last row, return the best value in the table.

Why it works

Moving both robots simultaneously is what keeps the state to two columns instead of two independent positions in time — the original Cherry Pickup needs a clever reparametrisation to achieve the same thing, but here the problem hands it to you. The n1 == n2 case is the only place the "emptied cell" rule bites, and double-counting there is the classic wrong answer.

Complexity

Time — O(rows · cols² · 9)
Space — O(cols²)

Pitfalls

A shared cell contributes once, not twice.
Unreachable column pairs must stay excluded, or they seed impossible paths with 0.
The robots may cross over each other; nothing forbids it.

Reference solution

Python

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    NEG = -1
    dp = [[NEG] * n for _ in range(n)]
    dp[0][n - 1] = grid[0][0] if n == 1 else grid[0][0] + grid[0][n - 1]
    for row in range(1, m):
        nxt = [[NEG] * n for _ in range(n)]
        for c1 in range(n):
            for c2 in range(n):
                if dp[c1][c2] == NEG:
                    continue
                for d1 in (-1, 0, 1):
                    for d2 in (-1, 0, 1):
                        n1, n2 = c1 + d1, c2 + d2
                        if not (0 <= n1 < n and 0 <= n2 < n):
                            continue
                        gain = grid[row][n1] if n1 == n2 else grid[row][n1] + grid[row][n2]
                        nxt[n1][n2] = max(nxt[n1][n2], dp[c1][c2] + gain)
        dp = nxt
    return max(0, max(max(r) for r in dp))

JavaScript

var cherryPickup = function(grid) {
    var m = grid.length, n = grid[0].length, NEG = -1, a, c1, c2;
    var dp = [];
    for (a = 0; a < n; a++) {
        var row0 = [];
        for (c2 = 0; c2 < n; c2++) row0.push(NEG);
        dp.push(row0);
    }
    dp[0][n - 1] = n === 1 ? grid[0][0] : grid[0][0] + grid[0][n - 1];
    for (var row = 1; row < m; row++) {
        var next = [];
        for (a = 0; a < n; a++) {
            var r2 = [];
            for (c2 = 0; c2 < n; c2++) r2.push(NEG);
            next.push(r2);
        }
        for (c1 = 0; c1 < n; c1++) {
            for (c2 = 0; c2 < n; c2++) {
                if (dp[c1][c2] === NEG) continue;
                for (var d1 = -1; d1 <= 1; d1++) {
                    for (var d2 = -1; d2 <= 1; d2++) {
                        var n1 = c1 + d1, n2 = c2 + d2;
                        if (n1 < 0 || n1 >= n || n2 < 0 || n2 >= n) continue;
                        var gain = n1 === n2 ? grid[row][n1] : grid[row][n1] + grid[row][n2];
                        var cand = dp[c1][c2] + gain;
                        if (cand > next[n1][n2]) next[n1][n2] = cand;
                    }
                }
            }
        }
        dp = next;
    }
    var best = 0;
    for (c1 = 0; c1 < n; c1++) {
        for (c2 = 0; c2 < n; c2++) if (dp[c1][c2] > best) best = dp[c1][c2];
    }
    return best;
};

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

All 667 arrays problems · the whole catalogue