LeetCode 931. 下降路径最小和

2021-08-03 HGNULB 约 11 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 931. 下降路径最小和

题意分析

给一个 n×n 的方阵，从第一行任意一个格子出发，每次只能走到下一行的正下方、左下方或右下方三个格子之一，一直走到最后一行，要求所有可能走法里元素和最小的那个值。起点不固定、终点也不固定，这是本题和「固定左上角走到固定右下角」那一类网格题最大的差别：两端都要取遍所有列。

移动规则决定了依赖方向是严格单向的——第 i 行的格子只依赖第 i-1 行，且只依赖相邻的至多三列。这种「只往下、不回头」的性质意味着不存在环，也就不需要任何搜索或松弛机制，按行推进一遍即可。

约束里 n 最大 100，格子的值在 -100 到 100 之间。值可以为负是一个重要信号：不能假设路径和随着行数递增而单调增大，也不能用「贪心走当前最小」来剪枝，因为一个很负的格子可能藏在看起来不划算的分支后面；同时全负矩阵下答案也是负数，任何以 0 作为初始最优值的写法都会出错。

边界上要考虑：n 可以等于 1，此时答案就是那唯一一个格子的值；第 0 列没有左上方来源、第 n-1 列没有右上方来源，转移时必须区别对待；最终答案要在最后一行的所有列里取最小，而不是某个固定位置。

解法：动态规划状态转移

核心思路

暴力做法是从第一行的每个格子出发做深度优先搜索，每层有三种分支，总路径数是 $O(n \cdot 3^{n-1})$，n = 100 时是个天文数字。

瓶颈在于大量子问题被重复计算：走到第 5 行第 3 列这个位置时，后续怎么走完全只取决于「当前在第 5 行第 3 列」这一个事实，与前面是从哪条路走过来的毫无关系。也就是说，一个格子被不同前缀路径反复到达，而每次都要把它下面的整棵搜索树重跑一遍。

由此得到状态定义：dp[i][j] 表示所有从第 0 行出发、终点落在第 i 行第 j 列的下降路径中，元素和的最小值。这个定义把「历史怎么来的」压缩成了一个数，正是消除重复的关键。

转移方程直接由移动规则倒推：能一步走到 (i, j) 的位置只有 (i-1, j-1)、(i-1, j)、(i-1, j+1) 三个（越界的不算），所以 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]。初始条件是第 0 行 dp[0][j] = matrix[0][j]，因为起点可以是第一行任意一列，代价就是格子自身。最终答案是 min(dp[n-1][j])，对最后一行所有列取最小。

再看依赖结构：第 i 行只用到第 i-1 行，第 i-2 行及以前的值再也不会被读取。于是可以只保留一行，用 dp 和 next 两个长度为 n 的数组滚动推进，空间从 $O(n^2)$ 降到 $O(n)$。这里的不变量是：每轮循环开始时，dp[j] 恰好是「终点落在上一行第 j 列」的最小路径和，循环体只负责由它推出本行的 next。

解题步骤

用 matrix[0] 的拷贝初始化 dp。第 0 行没有上一行可依赖，路径和就是格子本身。之所以要拷贝而不是直接引用 matrix[0]，是因为后面滚动时会整体替换 dp，如果第一步就指向输入的内部数组，某些写法（比如就地累加）会污染调用方的入参。

外层从第 1 行循环到第 n-1 行。第 0 行已经作为初始条件处理完毕，从 1 开始才有「上一行」可用；顺序必须自上而下，因为状态依赖方向就是自上而下的，逆序推进会读到还没算好的值。

每行新开一个 next 数组，而不是就地修改 dp。如果直接在 dp 上原地写，计算 next[j] 时会用到已经被本行覆盖过的 dp[j-1]，读到的是本行的值而不是上一行的，转移就串行了。开一个新数组是最不容易出错的写法，代价只是 $O(n)$ 的额外空间。

内层对每一列取三个来源的最小值。先把 best 置为正上方的 dp[j]（这一项永远存在，不需要判断），再用 j > 0 保护左上方的 dp[j-1]、用 j + 1 < n 保护右上方的 dp[j+1]。用「先取必然存在的那个，再有条件地收缩」这种写法，可以避免引入 Integer.MAX_VALUE 这类哨兵，也就不会在加上负数格子时出现溢出。

next[j] = best + matrix[i][j]。三个来源里选最小的那条路，再把当前格子的代价计进去，这一步就是转移方程的直译。

每行结束后 dp = next，完成滚动。这样下一轮的「上一行」就是刚算完的这一行，不变量继续成立。

最后在 dp 里取最小值返回。终点可以是最后一行的任意一列，所以不能返回 dp[0] 或 dp[n-1]。初值取 dp[0] 而不是 0 或某个大常数，是为了同时兼容全负矩阵和 n = 1 的情形。

以 matrix = [[2,1,3],[6,5,4],[7,8,9]] 走一遍：初始 dp = [2, 1, 3]。进入 i = 1 这一行，j = 0 时来源只有正上方 dp[0] = 2 与右上方 dp[1] = 1，最小是 1，next[0] = 1 + 6 = 7；j = 1 时三个来源 dp[0] = 2、dp[1] = 1、dp[2] = 3 齐全，最小是 1，next[1] = 1 + 5 = 6；j = 2 时来源是 dp[1] = 1 与 dp[2] = 3，最小是 1，next[2] = 1 + 4 = 5。滚动后 dp = [7, 6, 5]。进入 i = 2 这一行，j = 0 时来源 dp[0] = 7、dp[1] = 6，最小 6，next[0] = 6 + 7 = 13；j = 1 时来源 7、6、5，最小 5，next[1] = 5 + 8 = 13；j = 2 时来源 dp[1] = 6、dp[2] = 5，最小 5，next[2] = 5 + 9 = 14。滚动后 dp = [13, 13, 14]。最后在这一行取最小得到 13，对应的路径是 1 → 4 → 8（也可以是 1 → 5 → 7），手工相加正是 13。

代码实现

// 按行列顺序遍历每个格子，从已计算的相邻状态转移。
class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = Arrays.copyOf(matrix[0], n);

        for (int i = 1; i < n; i++) {
            int[] next = new int[n];
            for (int j = 0; j < n; j++) {
                int best = dp[j];
                if (j > 0) {
                    best = Math.min(best, dp[j - 1]);
                }
                if (j + 1 < n) {
                    best = Math.min(best, dp[j + 1]);
                }
                next[j] = best + matrix[i][j];
            }
            dp = next;
        }

        int answer = dp[0];
        for (int v : dp) {
            answer = Math.min(answer, v);
        }
        return answer;
    }
}

// 按行列顺序遍历每个格子，从已计算的相邻状态转移。
func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    dp := make([]int, n)
    copy(dp, matrix[0])

    for i := 1; i < n; i++ {
        next := make([]int, n)
        for j := 0; j < n; j++ {
            best := dp[j]
            if j > 0 && dp[j-1] < best {
                best = dp[j-1]
            }
            if j+1 < n && dp[j+1] < best {
                best = dp[j+1]
            }
            next[j] = best + matrix[i][j]
        }
        dp = next
    }

    answer := dp[0]
    for _, v := range dp {
        if v < answer {
            answer = v
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(n^2)$，其中 n 为矩阵边长。凭什么？外层遍历 n-1 行，内层遍历 n 列，每个格子只被计算一次，且单次计算是「最多两次比较加一次加法」的常数工作量；矩阵一共 $n^2$ 个格子，每个格子的状态算完就不再重算，因此总量与格子数同阶。

空间复杂度：$O(n)$。凭什么？滚动数组只保留上一行与当前行两个长度为 n 的数组，第 i-2 行及更早的状态在转移中永远不会被读到，可以安全丢弃；如果允许原地修改输入矩阵，把结果直接写回 matrix[i][j]，额外空间还能进一步降到 $O(1)$。

关键点总结

状态定义要把「终点在哪」写进去，而不是「怎么走过来的」：dp[i][j] 的语义是「以 (i, j) 为终点的最优值」，这一步抽象把指数级的路径集合压成了 $n^2$ 个数。凡是「路径的后续只取决于当前位置」的题，都可以照此定义。

起点或终点不唯一时，用多初值/多取值来处理，而不是加循环重跑：第一行整行都是合法起点，就把整行都设成初始状态；最后一行整行都是合法终点，就在整行里取最小。不要写「枚举起点，每次跑一遍 DP」，那会平白多出一个 n 倍。

遍历顺序必须与依赖方向一致：状态依赖上一行，就必须自上而下推进。写 DP 前先问「我依赖谁」，再决定循环方向，这比写完了调试要高效得多。

滚动数组的正确性来自依赖窗口：能压成一维，是因为第 i 行只依赖第 i-1 行这一层。但因为本行内的转移会读到相邻列，必须用「新数组 + 整体替换」而不是原地覆盖，否则会读到被本行污染的值。

有负数就不能用 0 或凭空的哨兵当初始最优值：最后取最小值时用 dp[0] 起手，天然适配全负矩阵；用 Integer.MAX_VALUE 当无效来源的哨兵则有加法溢出风险，改用条件判断更稳。

面试视角：这题是网格 DP 的入门模板，写对不加分，写不完整会扣分。稳妥的表达顺序是「先说状态定义，再说转移方程与初始条件，再说答案位置，最后说滚动优化」。答完可以主动提一句：若把三个来源改成「同一行不同列的任意位置」，就是 1289 的加强版，需要维护上一行的最小值与次小值把每行的 $O(n^2)$ 降到 $O(n)$。

易错点总结

错误写法：直接返回 dp[0] 或 dp[n-1]，不在最后一行取最小。用例 [[2,1,3],[6,5,4],[7,8,9]] → 最后一行状态是 [13, 13, 14]，返回 dp[n-1] 得到 14，正确答案是 13；终点列不固定，必须整行扫一遍。

错误写法：把答案初值设成 0 再与最后一行取最小。用例 [[1,2],[3,4]] → 最后一行状态是 [4, 5]，正确答案 4，但 0 比任何一项都小，函数直接返回 0；初值必须取自 dp 本身，dp[0] 是最简单的选择。

错误写法：原地在 dp 上覆盖而不用 next。用例 [[2,1,3],[6,5,4],[7,8,9]] → 计算第 1 行 j = 1 时，dp[0] 已经被本行的 7 覆盖，三来源变成 7、1、3，最小仍是 1 侥幸不出错；但把矩阵改成 [[1,9,9],[9,9,9],[9,9,9]] 后，j = 1 读到的 dp[0] 是本行刚算出的 10 而不是上一行的 1，结果会偏大。必须用新数组承接本行。

错误写法：边界判断写成 j >= 0 或 j + 1 <= n。用例任意 3×3 矩阵 → j = 0 时 j >= 0 为真，访问 dp[-1] 直接越界；j = n-1 时 j + 1 <= n 为真，访问 dp[n] 同样越界。正确的保护是 j > 0 与 j + 1 < n。

错误写法：把不存在的来源用 Integer.MAX_VALUE 填充后直接参与加法。用例第 0 列时若令左上方为 Integer.MAX_VALUE 并写成 Math.min(...) + matrix[i][j]，虽然 min 会把它挡掉，但如果误写成先加后比（MAX_VALUE + matrix[i][j]），在格子为正数时整型溢出成负数，会返回一个巨大的负值当作最优解。

错误写法：外层循环从 i = 0 开始。用例 [[2,1,3],[6,5,4],[7,8,9]] → 第 0 行会被再算一次，dp[0] 变成 min(2,1) + 2 = 3，第一行的值被重复累加，最终答案偏大；第 0 行是初始条件，不参与转移。

错误写法：以为可以贪心地每步走可达的最小格子。用例 [[1,2,3],[100,100,1],[100,100,1]] → 贪心从第一行最小的 1 出发，下一行可达的只有两个 100，总和 201；而从 3 出发走 3 → 1 → 1 只有 5，DP 给出的答案是 4（2 → 1 → 1）。局部最优不等于全局最优，必须把每一列的状态都算完。

错误写法：n = 1 时忘记处理，或在初始化前就访问第 1 行。用例 [[-5]] → 外层循环一次都不进，直接从 dp = [-5] 取最小返回 -5；若代码写成先访问 matrix[1] 再判断，会立即越界。初始化只依赖第 0 行，天然覆盖 n = 1。

错误写法：Go 里写 dp := matrix[0] 而不是 copy。这样 dp 与输入共享底层数组，虽然本实现每行都新建 next 不会写回，但一旦有人把优化成原地累加的版本合进来，就会静默修改调用方的 matrix，在多次调用同一份数据的测试里产生难查的错误。

错误写法：转移时漏掉右上方来源 dp[j+1]。用例 [[2,1,3],[6,5,4],[7,8,9]] → 第 1 行 j = 0 只剩正上方的 2，next[0] = 8 而不是 7，逐行传播下去最终答案变成 14，比正确的 13 大；三个来源方向缺一不可。

相似题目

题目	难度	考察点
64. 最小路径和	中等	起点终点都固定且只能右/下走，来源只有两个，不需要在末行取最小
120. 三角形最小路径和	中等	每行长度递增，来源只有正上方和左上方，且可自底向上推进免去末行取最小
1289. 下降路径最小和 II	困难	只禁止同列，来源是上一行除本列外的全部，需要维护最小值与次小值降复杂度
63. 不同路径 II	中等	转移是求和计数而非取最优，且要用障碍格把状态强制置零
174. 地下城游戏	困难	依赖方向必须反过来自右下往左上推，因为最优子结构在正向上不成立
1594. 矩阵的最大非负积	中等	转移是乘法，负负得正导致必须同时维护每格的最大值和最小值两条状态