Problem 29.8 · DP on GridsHard

Cherry Pickup II

What it teaches: Two walkers moving together: the state is (row, column 1, column 2).

Practise it on judges as “Cherry Pickup II”.

The problem

Two robots start at the top-left and top-right corners and each move down one row per step, to the same column or one column left or right. They collect cherries from the cells they visit (a shared cell counts once). Return the most cherries they can collect.

Example 1

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24

Constraints

2 ≤ rows, cols ≤ 70

Pattern clues in the wording

→ Two agents moving in lockstep
→ Shared cells count once

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int cherryPickup(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]	24
2	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]]	28

From slow to fast

Approaches

1. DP over (c1, c2) per row · O(rows × cols² × 9)

DP over (c1, c2) per row

Time O(rows × cols² × 9) Space O(cols²)

dp[c1][c2] = best total with robots at those columns in the current row (−1 = unreachable). For each next row, try all 9 predecessor pairs.

Approach 1

import java.util.Arrays;

class Solution {
    public int cherryPickup(int[][] grid) {
        int rows = grid.length, n = grid[0].length;
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, -1);
        dp[0][n - 1] = grid[0][0] + grid[0][n - 1];
        for (int r = 1; r < rows; r++) {
            int[][] next = new int[n][n];
            for (int[] row : next) Arrays.fill(row, -1);
            for (int a = 0; a < n; a++)
                for (int b = 0; b < n; b++) {
                    int best = -1;
                    for (int da = -1; da <= 1; da++)
                        for (int db = -1; db <= 1; db++) {
                            int pa = a + da, pb = b + db;
                            if (pa < 0 || pb < 0 || pa >= n || pb >= n) continue;
                            best = Math.max(best, dp[pa][pb]);
                        }
                    if (best < 0) continue;
                    next[a][b] = best + grid[r][a] + (a == b ? 0 : grid[r][b]);
                }
            dp = next;
        }
        int ans = 0;
        for (int[] row : dp) for (int x : row) ans = Math.max(ans, x);
        return ans;
    }
}

Verdict: Small state, many transitions.

Before you submit

Edge cases and common mistakes

Test these inputs

Robots meeting in the same cell
Two columns

Mistakes people make

Solving each robot separately and adding (double counts shared cells and ignores interaction).

Interview

Follow-up questions

How does the original Cherry Pickup (there and back on one grid) reduce to this?

Command Palette

The problem

Approaches

DP over (c1, c2) per row

Edge cases and common mistakes

Follow-up questions