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
- 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). - Both walkers take the same number of steps
s, so their rows determine their columns:c = s - r. - Let
dp[r1][r2]be the best total with the walkers in rowsr1andr2at the current step; a cell's cherry is added once, usingr1 != r2to detect distinct cells. - 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 (theif r1 != r2guard). - 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.