class Solution:
def cherryPickup(self, grid):
from functools import lru_cache
rows, cols = len(grid), len(grid[0])
@lru_cache(None)
def dp(r, c1, c2):
if c1 < 0 or c1 >= cols or c2 < 0 or c2 >= cols:
return float('-inf')
result = grid[r][c1]
if c1 != c2:
result += grid[r][c2]
if r != rows - 1:
temp = 0
for d1 in (-1, 0, 1):
for d2 in (-1, 0, 1):
temp = max(temp, dp(r+1, c1+d1, c2+d2))
result += temp
return result
return dp(0, 0, cols-1)
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int rows = grid.size(), cols = grid[0].size();
vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(cols, -1)));
function<int(int, int, int)> dfs = [&](int r, int c1, int c2) {
if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return INT_MIN;
if (dp[r][c1][c2] != -1) return dp[r][c1][c2];
int res = grid[r][c1];
if (c1 != c2) res += grid[r][c2];
if (r != rows - 1) {
int temp = 0;
for (int d1 = -1; d1 <= 1; ++d1) {
for (int d2 = -1; d2 <= 1; ++d2) {
temp = max(temp, dfs(r+1, c1+d1, c2+d2));
}
}
res += temp;
}
return dp[r][c1][c2] = res;
};
return dfs(0, 0, cols-1);
}
};
class Solution {
public int cherryPickup(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Integer[][][] dp = new Integer[rows][cols][cols];
return dfs(grid, 0, 0, cols - 1, dp);
}
private int dfs(int[][] grid, int r, int c1, int c2, Integer[][][] dp) {
int cols = grid[0].length, rows = grid.length;
if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return Integer.MIN_VALUE;
if (dp[r][c1][c2] != null) return dp[r][c1][c2];
int res = grid[r][c1];
if (c1 != c2) res += grid[r][c2];
if (r != rows - 1) {
int temp = 0;
for (int d1 = -1; d1 <= 1; d1++) {
for (int d2 = -1; d2 <= 1; d2++) {
temp = Math.max(temp, dfs(grid, r+1, c1+d1, c2+d2, dp));
}
}
res += temp;
}
dp[r][c1][c2] = res;
return res;
}
}
var cherryPickup = function(grid) {
const rows = grid.length, cols = grid[0].length;
const memo = new Map();
function dp(r, c1, c2) {
if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return -Infinity;
const key = r + ',' + c1 + ',' + c2;
if (memo.has(key)) return memo.get(key);
let result = grid[r][c1];
if (c1 !== c2) result += grid[r][c2];
if (r !== rows - 1) {
let temp = 0;
for (let d1 = -1; d1 <= 1; d1++) {
for (let d2 = -1; d2 <= 1; d2++) {
temp = Math.max(temp, dp(r+1, c1+d1, c2+d2));
}
}
result += temp;
}
memo.set(key, result);
return result;
}
return dp(0, 0, cols-1);
};
You are given a 2D grid of integers called grid where each cell represents the number of cherries at that position. Two robots start at the top row: one at the leftmost column (column 0) and the other at the rightmost column (column n-1). On each move, both robots move to the next row simultaneously, and each robot can move to the same column, or one column left or right (i.e., from column c, a robot can move to c-1, c, or c+1 in the next row).
When a robot visits a cell, it picks up all cherries from that cell. If both robots land on the same cell, only one can pick up the cherries (the cherries are counted only once).
The goal is to collect the maximum number of cherries possible as both robots move from the top to the bottom row. Each robot must move down to the next row in every step, and both must stay within the grid boundaries.
Key constraints:
0 and n-1 of the top row.The first idea that comes to mind is to simulate every possible path both robots can take from the top to the bottom, keeping track of the cherries collected. However, since each robot has 3 possible moves at every step (left, stay, right), and there are two robots, the number of possibilities grows exponentially with the number of rows. This brute-force approach quickly becomes infeasible for large grids.
We need a way to avoid recalculating results for the same positions. This is a classic scenario for dynamic programming (DP) with memoization. By storing the results for specific states (i.e., the row and columns of both robots), we can reuse them whenever we reach the same configuration again.
The core insight is to represent the state by three variables: the current row, and the columns of both robots. For each such state, we can recursively compute the maximum cherries that can be collected from that point onward, and store the result to avoid duplicate work.
dp(r, c1, c2) where r is the current row, and c1 and c2 are the current columns of robot 1 and robot 2, respectively.dp for the next row and new columns.dp(r, c1, c2) call in a memoization table or cache to avoid redundant calculations.dp(0, 0, n-1), representing both robots at the top row in their respective starting columns.This approach ensures that we explore all valid paths in an efficient manner, leveraging overlapping subproblems and optimal substructure properties of dynamic programming.
Let's consider a simple example:
grid = [
[3, 1, 1],
[2, 5, 1],
[1, 5, 5],
[2, 1, 1]
]
The DP table ensures that repeated subproblems (same row and columns for both robots) are only solved once.
m rows, there are 3^m possibilities per robot, or 9^m total combinations. This is infeasible for large grids.rows rows and cols columns for each robot, so the number of unique states is rows * cols * cols.O(rows * cols^2 * 9) simplifies to O(rows * cols^2) since 9 is a constant.O(rows * cols^2) for the memoization table.The "Cherry Pickup II" problem is a classic example of dynamic programming with multiple agents. By representing the state with the current row and columns of both robots, and using memoization to store results of subproblems, we avoid redundant computation and efficiently solve the problem. The key insights are to avoid double-counting cherries when both robots land on the same cell and to explore all possible moves at each step. This DP approach transforms an exponential brute-force problem into a polynomial-time solution, making it both elegant and practical.