⚡Flashcard Drill➔
NeetCode #756LC-741Hard2-D Dynamic Programming
← Back to All Problems

#756 · #741 · Cherry Pickup(摘樱桃)

📌 Problem Statement & Constraints

Given an n x n grid where 0 is empty, 1 is a cherry, and -1 is a thorn (blocked), start at (0, 0), walk to (n-1, n-1) moving only right or down, then walk back to (0, 0) moving only left or up. A cell's cherry is collected once. Return the maximum cherries collected, or 0 if no path exists. Constraints: 1 <= n <= 50.

💡 Core Algorithmic Approaches

  1. The outbound and return trips together visit a set of cells; model them as two walkers moving simultaneously from (0, 0) to (n-1, n-1).
  2. Both walkers take the same number of steps s, so their rows determine their columns: c = s - r.
  3. Let dp[r1][r2] be the best total with the walkers in rows r1 and r2 at the current step; a cell's cherry is added once, using r1 != r2 to detect distinct cells.
  4. Each walker came from the row above or the same row, giving four predecessor combinations.

💻 Benchmark Python3 Implementation

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        NEG = float("-inf")
        # dp[r1][r2] with both walkers having taken the same number of steps
        dp = [[NEG] * n for _ in range(n)]
        dp[0][0] = grid[0][0]
        for s in range(1, 2 * n - 1):
            nxt = [[NEG] * n for _ in range(n)]
            for r1 in range(n):
                c1 = s - r1
                if c1 < 0 or c1 >= n or grid[r1][c1] == -1:
                    continue
                for r2 in range(n):
                    c2 = s - r2
                    if c2 < 0 or c2 >= n or grid[r2][c2] == -1:
                        continue
                    best = NEG
                    for pr1 in (r1, r1 - 1):
                        for pr2 in (r2, r2 - 1):
                            if 0 <= pr1 < n and 0 <= pr2 < n:
                                best = max(best, dp[pr1][pr2])
                    if best == NEG:
                        continue
                    gain = grid[r1][c1] + (grid[r2][c2] if r1 != r2 else 0)
                    nxt[r1][r2] = best + gain
            dp = nxt
        return max(0, dp[n - 1][n - 1])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^3): O(n^2) states per step across O(n) steps.
💾 Space Complexity
O(n^2): two r1 x r2 layers.

⚠️ Interview Pitfalls & Follow-ups

  • Simulating the two trips independently: the forward and return paths share cells, so the two-walker formulation is needed to avoid double counting.
  • Adding both cherries when r1 == r2: the walkers then occupy the same cell, so its cherry counts once (the if r1 != r2 guard).
  • Treating thorns as passable: cells with -1 are blocked and must be skipped entirely.
  • Returning a negative value: if no path exists the answer is 0, hence max(0, ...).
⚡
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