LeetCode 1289. 下降路径最小和 II
目录
题目描述
题意分析
给一个 $n \times n$ 的整数矩阵，从第一行任选一格出发，每次向下走一行，要求相邻两行选的列号不能相同（可以跳到任意其他列，不限于相邻列），一直走到最后一行，求路径上元素之和的最小值。
「列号不同即可，不限相邻」是本题与经典下降路径题的唯一区别，却完全改变了转移的形态：经典版每格只能来自上一行的三个位置，是常数个来源；本题每格可以来自上一行的 $n-1$ 个位置，来源数量随 n 增长。
数据规模：$n$ 最多 200，矩阵元素在 $[-99, 99]$。$n^2 = 4 \times 10^4$，而朴素转移是 $O(n^3) = 8 \times 10^6$，其实也能过——但这道题被标为困难，考的正是能否把它降到 $O(n^2)$。
元素可以为负，这一点很重要：它排除了任何「路径和单调递增」的假设，也意味着不能用「只要挑最小的往下走」这种局部贪心，必须真正做完整的状态转移。
边界：$n = 1$（只有一格，答案就是它本身，且不存在「列号不同」的约束）、上一行存在多个相同的最小值、全负矩阵。
解法：DP + 维护两小值
核心思路
令
\[next[j] = grid[i][j] + \min_{k \ne j} dp[k]\]dp[j]表示走到上一行第j列时的最小路径和。当前行第j列不能接在上一行同列之后，因此朴素转移是：若每个
j都扫描上一行，时间复杂度是 $O(n^3)$。真正需要的只有上一行的最小值min1、其列号minCol，以及排除该位置后的最小值min2：当前列不是minCol时接min1，否则接min2。这里的
min2是按位置排第二，而不是严格不同的第二小数值。若上一行是[6,6,7]，排除第一个 6 后仍可使用另一个 6，所以应有min1 = min2 = 6。不变量：处理第
i行前，dp[j]是到达第i-1行第j列的最优值；扫描dp后，min1/minCol/min2能在排除任意一列时给出合法最小值。由此计算出的next[j]枚举了所有合法前驱并取到最优。正确性：对第一行结论显然成立。假设
dp对上一行正确，任意到达当前格的路径都必须来自某个不同列，其最优前缀恰由上述最小值或次小值给出；反之该前驱对应一条合法路径。因此next对当前行正确，归纳到最后一行后取最小值即为答案。
解题步骤
- 用第一行初始化
dp。- 对每个后续行，先完整扫描旧
dp，求min1、minCol、min2。- 对当前行每一列
j，若j == minCol就加min2，否则加min1，写入新数组next。- 用
next替换dp；所有行完成后返回dp的最小值。样例
[[1,2,3],[4,5,6],[7,8,9]]：第一轮得到[6,6,7]；此时两个最小值都为 6，下一轮得到[13,14,15]，答案是 13。反例也来自这一步：若把次小值定义成“严格大于最小值”，面对
[6,6,7]会错误地取 7。转移到下一行第 0 列时本可使用第 1 列的 6，却会被迫使用 7。
代码实现
class Solution {
public int minFallingPathSum(int[][] grid) {
int n = grid.length;
int[] dp = new int[n];
for (int j = 0; j < n; j++) {
dp[j] = grid[0][j];
}
for (int i = 1; i < n; i++) {
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
int minCol = -1;
for (int j = 0; j < n; j++) {
int v = dp[j];
if (v < min1) {
min2 = min1;
min1 = v;
minCol = j;
} else if (v < min2) {
min2 = v;
}
}
int[] ndp = new int[n];
for (int j = 0; j < n; j++) {
int add = j == minCol ? min2 : min1;
ndp[j] = grid[i][j] + add;
}
dp = ndp;
}
int answer = dp[0];
for (int v : dp) {
answer = Math.min(answer, v);
}
return answer;
}
}
func minFallingPathSum(grid [][]int) int {
n := len(grid)
dp := make([]int, n)
copy(dp, grid[0])
for i := 1; i < n; i++ {
min1, min2 := int(^uint(0)>>1), int(^uint(0)>>1)
minCol := -1
for j := 0; j < n; j++ {
v := dp[j]
if v < min1 {
min2 = min1
min1 = v
minCol = j
} else if v < min2 {
min2 = v
}
}
ndp := make([]int, n)
for j := 0; j < n; j++ {
add := min1
if j == minCol {
add = min2
}
ndp[j] = grid[i][j] + add
}
dp = ndp
}
answer := dp[0]
for _, v := range dp {
if v < answer {
answer = v
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n^2)$。每行各用一次线性扫描求两小值、一次线性扫描完成转移。
- 空间复杂度：$O(n)$。只保留上一行和当前行的状态。
关键点总结
- “排除一个位置后取最小值”只需最小值、最小值位置和按位置计的次小值。
- 重复最小值必须保留：次小值允许等于最小值。
- 先统计完整旧行，再写新行，避免滚动数组的新旧状态混用。
- 最后一行的落点不固定，必须再取一次全行最小值。
易错点总结
- 次小值要求严格大于最小值：样例第二轮会把
[6,6,7]的次小值错算为 7，答案从 13 变成 14。- 所有列都接
min1：样例会得到非法同列路径1 + 4 + 7 = 12。- 在同一个
dp上原地转移：后面的列会读到当前行的新值，破坏“只依赖上一行”的状态定义。- 两小值没有按行重置，或初始化为 0：负数矩阵会读到不存在的前驱值。
- 直接返回固定列：最优路径可以结束在最后一行任意列。
n = 1时不应执行跨行转移，答案就是唯一格子。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 931. 下降路径最小和 | 中等 | 只能落到相邻三列，来源是常数个，不需要次小值优化 |
| 64. 最小路径和 | 中等 | 只能向右或向下，依赖两个方向，边界行列要单独初始化 |
| 120. 三角形最小路径和 | 中等 | 每行长度递增，自底向上推导可以省掉边界判断 |
| 174. 地下城游戏 | 困难 | 状态必须倒着定义为「所需初始值」，正向 DP 会因负值失效 |