NeetCode #735LC-931Medium2-D Dynamic Programming
← Back to All Problems#735 · #931 · Minimum Falling Path Sum(下降路径最小和)
📌 Problem Statement & Constraints
Given an
n x n matrix, a falling path starts at any cell of the first row and moves to the next row choosing a column that differs by at most 1. Return the minimum sum of a falling path. Constraints: 1 <= n <= 100, -100 <= matrix[i][j] <= 100.💡 Core Algorithmic Approaches
- Process rows top to bottom;
dp[c]is the minimum falling-path sum ending at columncof the current row. - The only predecessors of
(r, c)are(r-1, c-1),(r-1, c)and(r-1, c+1), so take the minimum of those three. - The first row is the base case: every cell can start a path, so
dp = matrix[0]. - The answer is the minimum over the last row's
dpvalues.
💻 Benchmark Python3 Implementation
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
n = len(matrix)
dp = matrix[0][:] # any first-row cell may start the path
for r in range(1, n):
nxt = [0] * n
for c in range(n):
best = dp[c] # straight down
if c > 0:
best = min(best, dp[c - 1])
if c + 1 < n:
best = min(best, dp[c + 1])
nxt[c] = best + matrix[r][c]
dp = nxt
return min(dp)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): each of the n rows does O(n) constant-time work.
💾 Space Complexity
O(n): only the previous row's costs are retained.
⚠️ Interview Pitfalls & Follow-ups
- Assuming the path must start at
matrix[0][0]: it may start at any cell of the first row, which is why the base case is the whole first row. - Widening the column window: the move is limited to
-1, 0, +1; allowing a larger jump changes the answer. - Mutating the input matrix as the DP table: it happens to work, but it obscures the boundary handling and makes the code harder to reason about.
- Initialising with
infand forgetting the first row: starting frommatrix[0]removes the need for any special-cased first row.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.