Cherry Pickup II
Hard · 1-D Dynamic Programming · Explanation and code example
Dynamic Programming (Space Optimized)
How it works
Since each row's computation only depends on the row below it, we do not need to store the entire 3D array. We can use two 2D arrays: one for the current row and one for the previous row (the row below). After processing each row, we swap them. This reduces space complexity from O(n * m^2) to O(m^2).
Steps
- Create a 2D
dparray of size[COLS][COLS]for the previous row's results. - Process rows from bottom to top.
- For each row, create a new 2D
cur_dparray for the current row. - For each
(c1, c2)pair wherec1 <= c2:- Calculate cherries at current positions.
- Look at all 9 next positions in the
dparray (previous row). - Take the maximum and add current cherries.
- After processing the row, set
dp = cur_dp. - Return
dp[0][COLS-1].
Complexity
- Time complexity:
O(n * m ^ 2) - Space complexity:
O(m ^ 2)
Where
nis the number of rows andmis the number of columns in the grid.
Things to watch for
Double Counting Cherries When Robots Overlap
Forgetting to check if both robots land on the same cell and counting cherries twice. When c1 == c2, you must only add grid[r][c1] once, not grid[r][c1] + grid[r][c2].
Using 4 Directions Instead of 3
Treating this like a general grid traversal where robots can move in any direction. Each robot can only move down-left, down, or down-right (3 choices), not up or stay in place. This gives 9 total combinations per step, not 16.
Incorrect State Space for Memoization
Using only (r, c1) or (r, c2) for caching, forgetting that the state depends on both robot positions simultaneously. The correct state is (r, c1, c2) since both robots move together row by row.
Off-by-One Error on Base Case
Checking r == ROWS instead of r == ROWS - 1 for the base case. Since indexing is 0-based, the last row is at index ROWS - 1, and that is where you should collect final cherries and stop recursion.
Python code example
from typing import List
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
dp = [[0] * COLS for _ in range(COLS)]
for r in reversed(range(ROWS)):
cur_dp = [[0] * COLS for _ in range(COLS)]
for c1 in range(COLS):
for c2 in range(c1, COLS):
max_cherries = 0
cherries = grid[r][c1] + (grid[r][c2] if c1 != c2 else 0)
for d1 in [-1, 0, 1]:
for d2 in [-1, 0, 1]:
nc1, nc2 = c1 + d1, c2 + d2
if 0 <= nc1 < COLS and 0 <= nc2 < COLS:
max_cherries = max(max_cherries, cherries + dp[nc1][nc2])
cur_dp[c1][c2] = max_cherries
dp = cur_dp
return dp[0][COLS - 1]
C++ code example
class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int ROWS = grid.size(), COLS = grid[0].size();
vector<vector<int>> dp(COLS, vector<int>(COLS, 0));
for (int r = ROWS - 1; r >= 0; r--) {
vector<vector<int>> cur_dp(COLS, vector<int>(COLS, 0));
for (int c1 = 0; c1 < COLS; c1++) {
for (int c2 = c1; c2 < COLS; c2++) {
int maxCherries = 0;
int cherries = grid[r][c1] + (c1 == c2 ? 0 : grid[r][c2]);
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 < COLS && nc2 >= 0 && nc2 < COLS) {
maxCherries = max(maxCherries, cherries + dp[nc1][nc2]);
}
}
}
cur_dp[c1][c2] = maxCherries;
}
}
dp = cur_dp;
}
return dp[0][COLS - 1];
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.