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

  1. Let dp[c] be the minimum path sum ending at column c of the current row.
  2. The transition needs the minimum over all previous columns except c, which is the global minimum unless that minimum is in column c itself.
  3. So track the smallest and second-smallest values of the previous row together with the column index of the smallest.
  4. For each column, use the smallest value when c differs 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 idx1 you 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems