NeetCode #758LC-1289Hard2-D Dynamic Programming
← Back to All Problems#758 · #1289 · Minimum Falling Path Sum II(下降路径最小和 II)
📌 Problem Statement & Constraints
Given an
n x n grid, a falling path picks one cell per row, and the column chosen in row r + 1 must differ from the column chosen in row r. Return the minimum sum of a falling path. Constraints: 1 <= n <= 200, -99 <= grid[i][j] <= 99.💡 Core Algorithmic Approaches
- Let
dp[c]be the minimum path sum ending at columncof the current row. - The transition needs the minimum over all previous columns except
c, which is the global minimum unless that minimum is in columncitself. - So track the smallest and second-smallest values of the previous row together with the column index of the smallest.
- For each column, use the smallest value when
cdiffers from that index, otherwise the second smallest; add the current cell.
💻 Benchmark Python3 Implementation
class Solution:
def minFallingPathSum(self, grid: List[List[int]]) -> int:
n = len(grid)
dp = grid[0][:]
for r in range(1, n):
# find the two smallest previous values and the column of the smallest
best1 = best2 = float("inf")
idx1 = -1
for c in range(n):
v = dp[c]
if v < best1:
best2 = best1
best1 = v
idx1 = c
elif v < best2:
best2 = v
nxt = [0] * n
for c in range(n):
prev = best1 if c != idx1 else best2
nxt[c] = prev + grid[r][c]
dp = nxt
return min(dp)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): each row finds the top-two values and then builds the next row.
💾 Space Complexity
O(n): one row of costs.
⚠️ Interview Pitfalls & Follow-ups
- Taking the global minimum every row: the column must differ from the previous row's column, so when the minimum is in the same column you must fall back to the second smallest.
- Sorting each row: that is O(n log n) per row; tracking the two smallest values is O(n).
- Forgetting the index of the minimum: without
idx1you cannot tell whether the forbidden column was the minimising one. - Special-casing
n == 1: the loop simply does not run and the single cell is the answer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.