LeetCode 1289: Minimum Falling Path Sum II ·

基本資料
#

難易度: hard 第一次嘗試：2026-07-05 來源：Day 34 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 1289: pass after state-vs-optimization repair
explain LC 1289 with the exact state and why the min/second-min optimization is needed

當天筆記摘錄
#

Problem 1 - LC 1289 Minimum Falling Path Sum II
#

Pattern: row-by-row optimization DP with forbidden same-column reuse.

Why This Fits
#

This is still DP because:

the path is built one row at a time
the best answer for the current row depends only on the previous row

But the rule changed:

the next row cannot choose the same column as the previous row

The naive recurrence is still correct:

dp[r][c] = grid[r][c] + min(dp[r - 1][prev_c] for all prev_c != c)

But that costs O(n) per cell and becomes:

O(n^3)

Core State / Invariant
#

dp[r][c] = minimum falling path sum ending at row r, column c,
subject to not using the same column in adjacent rows

Key Optimization
#

For the previous row, track:

smallest value
column of that smallest value
second-smallest value

Then for current column c:

if c is not the min column from the previous row, use previous-row min
otherwise use previous-row second min

Optimized Transition
#

dp[r][c] = grid[r][c] + (
    prev_min if c != prev_min_col else prev_second_min
)

Base Case
#

First row:

dp[0][c] = grid[0][c]

Final Answer
#

min(dp[last_row][c] for all c)

Complexity
#

Naive:

Time: O(n^3)
Space: O(n^2)

Optimized:

Time: O(n^2)
Space: O(n^2)

Can be compressed to:

Space: O(n)

Common Mistakes
#

giving the naive recurrence but not noticing it is too slow
forgetting why second-minimum is needed
mixing up min value with min column
returning one fixed cell instead of the min of the last row

Strong Spoken Explanation
#

I still define dp[r][c] as the minimum valid falling path sum ending at (r, c), but the constraint is that adjacent rows cannot use the same column. The naive transition checks every previous-row column except c, which is correct but too slow. The optimization is to keep the smallest and second-smallest DP values from the previous row. Then for each current column, I use the previous-row minimum unless it came from the same column, in which case I use the second minimum. That reduces the time from O(n^3) to O(n^2).

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        prev = grid[0][:]

        for r in range(1, n):
            min1 = min2 = float('inf')
            idx1 = -1
            for c, val in enumerate(prev):
                if val < min1:
                    min2 = min1
                    min1 = val
                    idx1 = c
                elif val < min2:
                    min2 = val

            curr = [0] * n
            for c in range(n):
                best_prev = min2 if c == idx1 else min1
                curr[c] = grid[r][c] + best_prev
            prev = curr

        return min(prev)