What is the best pattern for Minimum Falling Path Sum?

The best pattern is state transition dynamic programming on a matrix. Each cell stores the minimum path sum ending there, using the three reachable cells from the previous row.

Why does greedy not work for this problem?

A locally small move can lead into large values later, while a slightly larger move now may open a much smaller total path below. Minimum Falling Path Sum needs full DP because the optimal substructure depends on cumulative sums, not per-step minimum choices.

Can I solve Minimum Falling Path Sum in place?

Yes, you can update the matrix row by row if modifying the input is allowed. Since each row only depends on the row above, in-place DP works as long as you never overwrite values that are still needed as predecessors.

What are the edge cases to watch in this matrix DP?

Single-cell matrices return that one value immediately, and negative numbers can make the minimum path strongly non-intuitive. The most common edge bug is mishandling the first and last columns, where only two predecessor positions may exist.

How do I reduce space in this state transition dynamic programming solution?

Keep only one array for the previous row and build a new array for the current row. After finishing the row, replace the previous array, which reduces extra space from `O(n^2)` to `O(n)` while preserving the same transition logic.

#931

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

下降路径最小和

给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径的最小和。下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位…

数组动态规划矩阵

题目描述

给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径

提示：

n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示从第一行开始下降，到达第 $i$ 行第 $j$ 列的最小路径和。那么我们可以得到这样的动态规划转移方程：

f[i][j] = matrix[i][j] + \min \left\{ \begin{aligned} & f[i - 1][j - 1], & j > 0 \\ & f[i - 1][j], & 0 \leq j < n \\ & f[i - 1][j + 1], & j + 1 < n \end{aligned} \right.

最终的答案即为 $\min \limits_{0 \leq j < n} f[n - 1][j]$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。

我们注意到，状态 $f[i][j]$ 只与上一行的状态有关，因此我们可以使用滚动数组的方式，去掉第一维的状态，将空间复杂度优化到 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        f = [0] * n
        for row in matrix:
            g = [0] * n
            for j, x in enumerate(row):
                l, r = max(0, j - 1), min(n, j + 2)
                g[j] = min(f[l:r]) + x
            f = g
        return min(f)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want a DP state that is tied to position, not path enumeration, because each move depends only on the previous row.
question_mark
They are checking whether you spot the three-source transition and handle edge columns without branching bugs.
question_mark
They may ask for space optimization after the full-table solution, since the matrix transition only needs one prior row.

warning

常见陷阱

外企场景

error
Using a greedy choice per row fails because the smallest immediate next value may block a better total path later.
error
Forgetting boundary checks at column `0` or `n - 1` causes invalid predecessor access or incorrect minimums.
error
Mutating values in the wrong order during space optimization can mix current-row updates with previous-row states.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the maximum falling path sum instead of the minimum by flipping the transition aggregator from `min` to `max`.
arrow_right_alt
Allow additional moves, such as two columns away, which changes the transition set but keeps the same row-based DP pattern.
arrow_right_alt
Reconstruct the actual minimum path, not just the sum, by storing parent pointers alongside each DP state.

help

常见问题

外企场景

继续练习

#773 滑动谜题 #741 摘樱桃 #1139 最大的以 1 为边界的正方形