Cherry Pickup II

hard array dp matrix

Problem

Two robots start at (0,0) and (0,n-1) on an m x n grid. Each step, each robot moves down one row to one of 3 adjacent columns. Maximize the total cherries collected (they don't double-count when on the same cell).

Inputgrid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]

Output24

Both robots sweep optimal columns picking 24 cherries.

grid (JSON)

def cherry_pickup(grid):
    m, n = len(grid), len(grid[0])
    NEG = float('-inf')
    dp = [[NEG] * n for _ in range(n)]
    dp[0][n-1] = grid[0][0] + (grid[0][n-1] if n > 1 else 0)
    for r 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):
                        nc1, nc2 = c1 + d1, c2 + d2
                        if 0 <= nc1 < n and 0 <= nc2 < n:
                            add = grid[r][nc1] + (grid[r][nc2] if nc1 != nc2 else 0)
                            nxt[nc1][nc2] = max(nxt[nc1][nc2], dp[c1][c2] + add)
        dp = nxt
    return max(max(row) for row in dp)

function cherryPickup(grid) {
  const m = grid.length, n = grid[0].length;
  let dp = Array.from({length: n}, () => new Array(n).fill(-Infinity));
  dp[0][n-1] = grid[0][0] + (n > 1 ? grid[0][n-1] : 0);
  for (let r = 1; r < m; r++) {
    const nxt = Array.from({length: n}, () => new Array(n).fill(-Infinity));
    for (let c1 = 0; c1 < n; c1++) for (let c2 = 0; c2 < n; c2++) {
      if (dp[c1][c2] === -Infinity) continue;
      for (let d1 = -1; d1 <= 1; d1++) for (let d2 = -1; d2 <= 1; d2++) {
        const nc1 = c1 + d1, nc2 = c2 + d2;
        if (nc1 < 0 || nc1 >= n || nc2 < 0 || nc2 >= n) continue;
        const add = grid[r][nc1] + (nc1 !== nc2 ? grid[r][nc2] : 0);
        if (dp[c1][c2] + add > nxt[nc1][nc2]) nxt[nc1][nc2] = dp[c1][c2] + add;
      }
    }
    dp = nxt;
  }
  let best = 0;
  for (const row of dp) for (const v of row) if (v > best) best = v;
  return best;
}

class Solution {
    public int cherryPickup(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[n][n];
        for (int[] r : dp) Arrays.fill(r, Integer.MIN_VALUE);
        dp[0][n-1] = grid[0][0] + (n > 1 ? grid[0][n-1] : 0);
        for (int r = 1; r < m; r++) {
            int[][] nxt = new int[n][n];
            for (int[] x : nxt) Arrays.fill(x, Integer.MIN_VALUE);
            for (int c1 = 0; c1 < n; c1++) for (int c2 = 0; c2 < n; c2++) {
                if (dp[c1][c2] == Integer.MIN_VALUE) continue;
                for (int d1 = -1; d1 <= 1; d1++) for (int d2 = -1; d2 <= 1; d2++) {
                    int nc1 = c1 + d1, nc2 = c2 + d2;
                    if (nc1 < 0 || nc1 >= n || nc2 < 0 || nc2 >= n) continue;
                    int add = grid[r][nc1] + (nc1 != nc2 ? grid[r][nc2] : 0);
                    nxt[nc1][nc2] = Math.max(nxt[nc1][nc2], dp[c1][c2] + add);
                }
            }
            dp = nxt;
        }
        int best = 0;
        for (int[] row : dp) for (int v : row) best = Math.max(best, v);
        return best;
    }
}

int cherryPickup(vector>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector> dp(n, vector(n, INT_MIN));
    dp[0][n-1] = grid[0][0] + (n > 1 ? grid[0][n-1] : 0);
    for (int r = 1; r < m; r++) {
        vector> nxt(n, vector(n, INT_MIN));
        for (int c1 = 0; c1 < n; c1++) for (int c2 = 0; c2 < n; c2++) {
            if (dp[c1][c2] == INT_MIN) continue;
            for (int d1 = -1; d1 <= 1; d1++) for (int d2 = -1; d2 <= 1; d2++) {
                int nc1 = c1 + d1, nc2 = c2 + d2;
                if (nc1 < 0 || nc1 >= n || nc2 < 0 || nc2 >= n) continue;
                int add = grid[r][nc1] + (nc1 != nc2 ? grid[r][nc2] : 0);
                nxt[nc1][nc2] = max(nxt[nc1][nc2], dp[c1][c2] + add);
            }
        }
        dp = nxt;
    }
    int best = 0;
    for (auto& row : dp) for (int v : row) best = max(best, v);
    return best;
}

Explanation

Two robots fall down the grid at the same speed, so they are always on the same row. That lets us track just their two column positions and walk the grid row by row together.

The state is dp[c1][c2] = the most cherries collected so far when robot 1 is in column c1 and robot 2 is in column c2 on the current row. We start with dp[0][n-1] (top-left and top-right corners) holding the cherries of those two starting cells.

To move to the next row, each robot may shift to one of 3 columns (-1, 0, +1), giving 9 column-pair combinations. For each, we add the cherries of the two new cells, but if both robots land on the same cell (nc1 == nc2) we count it only once. We keep the best value into nxt[nc1][nc2].

After processing every row, the answer is the largest value anywhere in the final dp table — the best place for the robots to finish.

Example: for grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]], the two robots sweep their best columns and collect 24 cherries.

Time: O(m·n^2) Space: O(n^2)