What is a falling path with non-zero shifts?

A falling path selects one element per row such that consecutive elements are never in the same column, enforcing a non-zero column shift.

How does state transition dynamic programming apply here?

Each cell's minimum path sum depends on the minimum values from the previous row excluding the same column, forming a classic DP state transition.

Can space be optimized in Minimum Falling Path Sum II?

Yes, by using two arrays for current and previous rows instead of a full DP matrix, space is reduced to O(N).

Why track the smallest and second smallest values?

Tracking these values allows fast selection of the minimum excluding the current column without scanning all previous columns.

What is the time complexity for this approach?

The optimized DP approach runs in O(N^2) time, processing each row and column while efficiently handling the column exclusion.

#1289

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

下降路径最小和 II

给你一个 n x n 整数矩阵 grid ，请你返回非零偏移下降路径数字和的最小值。非零偏移下降路径定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。示例 1：输入： grid = [[1,2,3],[4,5,6],[7,8,9]] 输…

数组动态规划矩阵

题目描述

给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。

示例 2：

输入：grid = [[7]]
输出：7

提示：

n == grid.length == grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示前 $i$ 行，且最后一个数字在第 $j$ 列的最小数字和。那么状态转移方程为：

f[i][j] = \min_{k \neq j} f[i - 1][k] + grid[i - 1][j]

其中 $k$ 表示第 $i - 1$ 行的数字在第 $k$ 列，第 $i$ 行第 $j$ 列的数字为 $grid[i - 1][j]$ 。

最后答案为 $f[n]$ 中的最小值。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为矩阵的行数。

我们注意到，状态 $f[i][j]$ 只与 $f[i - 1][k]$ 有关，因此我们可以使用滚动数组优化空间复杂度，将空间复杂度优化到 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        f = [0] * n
        for row in grid:
            g = row[:]
            for i in range(n):
                g[i] += min((f[j] for j in range(n) if j != i), default=0)
            f = g
        return min(f)

speed

复杂度分析

指标	值
时间	complexity is O(N^2) because each cell requires scanning N previous elements, optimized by tracking smallest and second smallest values. Space can be reduced to O(N) by reusing row arrays instead of a full DP matrix.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Are you enforcing the non-zero column shift in your state transitions?
question_mark
Can you optimize your DP to reduce space while maintaining correctness?
question_mark
How do you handle ties for minimum values when skipping the same column?

warning

常见陷阱

外企场景

error
Forgetting to exclude the same column in consecutive rows, leading to invalid paths.
error
Using full N x N DP without optimization, causing unnecessary space usage.
error
Incorrectly updating the minimum when multiple columns share the smallest value.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow negative and positive values, increasing the risk of selecting suboptimal paths.
arrow_right_alt
Compute the maximum falling path sum instead of minimum, applying the same DP logic.
arrow_right_alt
Handle non-square matrices where row and column counts differ, requiring adjusted state tracking.

help

常见问题

外企场景

继续练习

#1277 统计全为 1 的正方形子矩阵 #1301 最大得分的路径数目 #1349 参加考试的最大学生数