前言
今天是我们讲解动态规划专题中的 路径问题 的第五天。
我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。
路径问题 我会按照编排好的顺序进行讲解（一天一道）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 DP 类型题目 ~
题目描述
这是 LeetCode 上的931. 下降路径最小和，难度为 Medium。
给你一个 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,1,3], [[2,1,3], [6,5,4], [6,5,4], [7,8,9]] [7,8,9]] 复制代码
示例 2：
输入：matrix = [[-19,57],[-40,-5]] 输出：-59 解释：下面是一条和最小的下降路径，用加粗标注： [[-19,57], [-40,-5]] 复制代码
示例 3：
输入：matrix = [[-48]] 输出：-48 复制代码
提示：
- n == matrix.length
- n == matrix[i].length
- 1 <= n <= 100
- -100 <= matrix[i][j] <= 100
动态规划(基于起点)
这题其实是 120.三角形最小路径和 的一道变形题。
在 120.三角形最小路径和 中，我们是从一个确定的起点出发，按照「某些条件」不断的进行转移，直到拿到一条「路径和最小」的路径。
本题则是能够从首行的任意位置开始转移。
我们可以定义一个 find() 函数，传入 矩阵 和 首行的起点下标，返回 以首行该下标 为起点的 最小路径和 。
那么答案就是所有的 find(matrix,i)find(matrix, i)find(matrix,i) 的最小值，i 的取值范围 [0,n)。代表能够从首行的任意下标出发。
而对于确定起点的最小路径和问题的求解，则是和我们昨天的 120.三角形最小路径和 分析方法完全一样。
由于我们需要先枚举起点，再进行 DP，这样做的复杂度是 O(n3)O(n^3)O(n3) 的。
本题数据只有 10210^2102，因此计算量是 10610^6106，是可以过的。
PS. 如果你还不了解如何根据 复杂度/计算量 来判断是否超时的话，可以看看 这篇文章 的总结部分。
代码：
class Solution { int MAX = Integer.MAX_VALUE; public int minFallingPathSum(int[][] mat) { int n = mat.length; int ans = MAX; // 枚举首行的每个下标作为「起点」 for (int i = 0; i < n; i++) { ans = Math.min(ans, find(mat, i)); } return ans; } // 返回以 (0, u) 作为起点的最小路径和 int find(int[][] mat, int u) { int n = mat.length; int[][] f = new int[n][n]; for (int i = 0; i < n; i++) f[0][i] = i == u ? mat[0][i] : MAX; for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { f[i][j] = MAX; int val = mat[i][j]; if (f[i-1][j] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j] + val); if (j - 1 >= 0 && f[i-1][j-1] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j-1] + val); if (j + 1 < n && f[i-1][j+1] != MAX) f[i][j] = Math.min(f[i][j], f[i-1][j+1] + val); } } int ans = MAX; for (int i = 0; i < n; i++) ans = Math.min(ans, f[n-1][i]); return ans; } } 复制代码
- 时间复杂度：枚举首行起点复杂度为 O(n)O(n)O(n)；对于一个确定的起点，找到其「最小路径和」的路径需要转移 O(n2)O(n^2)O(n2) 个状态，复杂度为 O(n2)O(n^2)O(n2)。整体复杂度为 O(n3)O(n^3)O(n3)。
- 空间复杂度：O(n2)O(n^2)O(n2)
动态规划(基于定义)
上述的解法，其实是基于我们 120.三角形最小路径和 的思路展开的。
而且算法的复杂度是 O(n3)O(n^3)O(n3)，那么是否有更优的做法呢？
上述的解法总的来说分为两步：
- 枚举起点
- DP 求某个起点的最小路径和
DP 过程的复杂度我们是无法优化了，那么枚举起点的过程是否可以优化（省掉）呢？
答案是可以的。我们可以直接从 DP 定义出发，进行转移即可。
定义 f[i][j]f[i][j]f[i][j] 为到达位置 (i,j)(i,j)(i,j) 的最小路径和。
那么最终答案为所有 f[n−1][i]f[n-1][i]f[n−1][i] 的最小值，i 的取值范围为 [0,n)。代表最小路径的结尾可能是最后一行的任意位置。
代码：
class Solution { int MAX = Integer.MAX_VALUE; public int minFallingPathSum(int[][] mat) { int n = mat.length; int[][] f = new int[n][n]; // 初始化：对于首行而言，每个位置的「最小成本」就是其「矩阵值」 for (int i = 0; i < n; i++) f[0][i] = mat[0][i]; // 从第二行开始，根据题目给定的条件进行转移 for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { int val = mat[i][j]; f[i][j] = f[i - 1][j] + val; if (j - 1 >= 0) f[i][j] = Math.min(f[i][j], f[i-1][j-1] + val); if (j + 1 < n) f[i][j] = Math.min(f[i][j], f[i-1][j+1] + val); } } int ans = MAX; for (int i = 0; i < n; i++) ans = Math.min(ans, f[n-1][i]); return ans; } } 复制代码
- 时间复杂度：O(n2)O(n^2)O(n2)
- 空间复杂度：O(n2)O(n^2)O(n2)
总结
如果考虑从「起点」出发，本题是在 120.三角形最小路径和 的基础上增加了一个「枚举起点」的考察点。
如果从「DP 状态定义」出发，那么这就是一题常规 DP 路径题。
有时候，我们会因为做过一些题目，很容易就代入已做过的题目的解法。
有时候这会让我们的思维很受限制，而且这样的解题方法往往会让算法复杂度会上升一个级别。
想想如果是在刚做完 120.三角形最小路径和 的情况下过来本题的话，大多数同学的第一想法会是去「枚举起点」，这是一个很人性的做法，在某个解决方案上堆逻辑。
使用做过的题目进行代入解题，其实本身没有问题。
但需要我们结合「复杂度/计算量」去分析是否超时。这点需要特别注意一下 ~
讲了好几天 DP 了，大家好好消化一下。周末愉快 ~
路径问题（目录）
62.不同路径（中等）：路径问题第一讲
63.不同路径 II（中等）：路径问题第二讲
64.最小路径和（中等）：路径问题第三讲
120.三角形最小路径和（中等）：路径问题第四讲
931.下降路径最小和（中等）：本篇
1289.下降路径最小和 II（困难）
1575.统计所有可行路径（困难）
576.出界的路径数（中等）
1301.最大得分的路径数目（困难）
欢迎补充 ~
最后
这是我们「刷穿 LeetCode」系列文章的第 No.931 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
