⚡Flashcard Drill➔
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

  1. Let dp[c1][c2] be the maximum cherries after the rows processed so far, with the robots in columns c1 and c2.
  2. Each robot moved from c-1, c, or c+1 in the previous row, so there are 9 predecessor combinations.
  3. Add grid[r][c1] + grid[r][c2], counting the cell once when c1 == c2.
  4. 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 == c2 they 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 == 1 incorrectly: 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 > c2 is perfectly allowed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems