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

  1. Process rows top to bottom; dp[c] is the minimum falling-path sum ending at column c of the current row.
  2. 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.
  3. The first row is the base case: every cell can start a path, so dp = matrix[0].
  4. The answer is the minimum over the last row's dp values.

💻 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 inf and forgetting the first row: starting from matrix[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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems