NeetCode #757LC-1463Hard2-D Dynamic Programming
← Back to All Problems#757 · #1463 · Cherry Pickup II(摘樱桃 II)
📌 Problem Statement & Constraints
Given a
rows x cols grid of cherries, two robots start at (0, 0) and (0, cols-1). Each step both move down one row, to a column within one of their current column. Collect cherries, counting each cell once. Return the maximum collected. Constraints: 1 <= rows, cols <= 70, 0 <= grid[i][j] <= 100.💡 Core Algorithmic Approaches
- Let
dp[c1][c2]be the maximum cherries after the rows processed so far, with the robots in columnsc1andc2. - Each robot moved from
c-1,c, orc+1in the previous row, so there are 9 predecessor combinations. - Add
grid[r][c1] + grid[r][c2], counting the cell once whenc1 == c2. - The answer is the maximum over all column pairs after the last row.
💻 Benchmark Python3 Implementation
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
NEG = float("-inf")
dp = [[NEG] * cols for _ in range(cols)]
dp[0][cols - 1] = grid[0][0] + grid[0][cols - 1]
if cols == 1:
dp[0][0] = grid[0][0] # both robots share the single column
for r in range(1, rows):
nxt = [[NEG] * cols for _ in range(cols)]
for c1 in range(cols):
for c2 in range(cols):
best = NEG
for p1 in (c1 - 1, c1, c1 + 1):
if p1 < 0 or p1 >= cols:
continue
for p2 in (c2 - 1, c2, c2 + 1):
if 0 <= p2 < cols:
best = max(best, dp[p1][p2])
if best == NEG:
continue
gain = grid[r][c1] + (grid[r][c2] if c1 != c2 else 0)
nxt[c1][c2] = best + gain
dp = nxt
return max(max(row) for row in dp)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(rows * cols^2): O(cols^2) states per row with 9 transitions each.
💾 Space Complexity
O(cols^2): two column-pair layers.
⚠️ Interview Pitfalls & Follow-ups
- Adding both cherries when the robots overlap: when
c1 == c2they share a cell, so it counts once. - Restricting each robot to the same column offset: they move independently within one column, so all 9 combinations are needed.
- Handling
cols == 1incorrectly: both robots start on the same cell, so the special case prevents double counting row 0. - Assuming the robots cannot cross: their columns are independent, so
c1 > c2is perfectly allowed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.