前言
今天是我们讲解动态规划专题中的 路径问题 的第三天。
今天讲解的题目主要是为了巩固 上一讲 我和你分享的 DP 分析技巧。
另外，我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。
路径问题 我按照编排好的顺序进行讲解（一天一道）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 DP 类型题目 ~
题目描述
这是 LeetCode 上的64. 最小路径和，难度为 Medium。
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。 复制代码
示例 2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12 复制代码
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
动态规划解法
这道题是在 62. 不同路径 的基础上，增加了路径成本概念。
我们可以根据问题来调整我们的「状态定义」：
定义 f[i][j] 为从 (0,0) 开始到达位置 (i,j) 的最小总和。
那么 f[n-1][m-1] 就是我们最终的答案，f[0][0]=grid[0][0] 是一个显而易见的起始状态。
由于题目限定了我们只能 往下 或者 往右 移动，因此我们按照当前位置可由哪些位置转移过来进行分析：
- 当前位置只能通过 往下 移动而来，即有
f[i][j] = f[i-1][j] + grid[i][j] - 当前位置只能通过 往右 移动而来，即有
f[i][j] = f[i][j-1] + grid[i][j] - 当前位置既能通过 往下 也能 往右 移动，即有
f[i][j] = min(f[i][j-1],f[i-1][j]) + grid[i][j]
代码：
class Solution { public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] f = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) { f[i][j] = grid[i][j]; } else { int top = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE; int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE; f[i][j] = Math.min(top, left); } } } return f[m - 1][n - 1]; } } 复制代码
- 时间复杂度：O(n∗m)O(n*m)O(n∗m)
- 空间复杂度：O(n∗m)O(n*m)O(n∗m)
进阶
- 如果要输出总和最低的路径呢？（如果有多个答案，返回其中之一即可）
从原问题我们知道，我们需要从 (0,0) 一步步转移到 (m-1,n-1)。
也就是我们需要扫描完整个方块（转移完所有的状态），才能得到答案。
那么显然，我们可以使用额外的数据结构来记录，我们是如何一步步转移到 f[m-1][n-1] 的。
当整个 dp 过程结束后，我们再用辅助记录的数据结构来回推我们的路径。
同时，由于我们原有的 dp 部分已经创建了一个二维数组来存储状态值，这次用于记录「上一步」的 g 数组我们改用一维数组来记录。
代码：
class Solution { int m, n; public int minPathSum(int[][] grid) { m = grid.length; n = grid[0].length; int[][] f = new int[m][n]; int[] g = new int[m * n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) { f[i][j] = grid[i][j]; } else { int top = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE; int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE; f[i][j] = Math.min(top, left); g[getIdx(i, j)] = top < left ? getIdx(i - 1, j) : getIdx(i, j - 1); } } } // 从「结尾」开始，在 g[] 数组中找「上一步」 int idx = getIdx(m - 1, n - 1); // 逆序将路径点添加到 path 数组中 int[][] path = new int[m + n][2]; path[m + n - 1] = new int[]{m - 1, n - 1}; for (int i = 1; i < m + n; i++) { path[m + n - 1 - i] = parseIdx(g[idx]); idx = g[idx]; } // 顺序输出位置 for (int i = 1; i < m + n; i++) { int x = path[i][0], y = path[i][1]; System.out.print("(" + x + "," + y + ") "); } System.out.println(" "); return f[m - 1][n - 1]; } int[] parseIdx(int idx) { return new int[]{idx / n, idx % n}; } int getIdx(int x, int y) { return x * n + y; } } 复制代码
也许你会觉得「输出」方案的代码太麻烦了。
这是因为我们找路径的过程是「倒着」找，而输出方案的时候则是「顺着」输出。
如果希望简化找路径的过程，我们需要对原问题进行等价转换：
将 「(0,0) 到 (m-1,n-1) 的最短路径」转换为「从 (m-1,n-1) 到 (0,0) 的最短路径」，同时移动方向从「向下 & 向右」转换为「向上 & 向左」。
这样我们就能实现「找路径」的顺序和「输出」顺序同向。
调整定义 f[i][j] 为从 (m-1,n-1) 开始到达位置 (i,j) 的最小总和。
class Solution { int m, n; public int minPathSum(int[][] grid) { m = grid.length; n = grid[0].length; int[][] f = new int[m][n]; int[] g = new int[m * n]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (i == m - 1 && j == n - 1) { f[i][j] = grid[i][j]; } else { int bottom = i + 1 < m ? f[i + 1][j] + grid[i][j] : Integer.MAX_VALUE; int right = j + 1 < n ? f[i][j + 1] + grid[i][j] : Integer.MAX_VALUE; f[i][j] = Math.min(bottom, right); g[getIdx(i, j)] = bottom < right ? getIdx(i + 1, j) : getIdx(i, j + 1); } } } int idx = getIdx(0,0); for (int i = 1; i <= m + n; i++) { if (i == m + n) continue; int x = parseIdx(idx)[0], y = parseIdx(idx)[1]; System.out.print("(" + x + "," + y + ") "); idx = g[idx]; } System.out.println(" "); return f[0][0]; } int[] parseIdx(int idx) { return new int[]{idx / n, idx % n}; } int getIdx(int x, int y) { return x * n + y; } } 复制代码
- 如果方块中存在负权，如何求解？
如果考虑方块中增加负权的话，自然还需要增加一个限制：每个格子只能访问一次，否则会存在无数次访问负权格子的路径。
这时候问题就转换为「图论」问题，变成一个「最小生成树」问题了。
将每个格子 往右 和 往下 两个方向看做两条无向边，使用 Prim算法/Kruskal算法 求解。
这部分我们在之后的图论再讲。
总结
今天，除了 LeetCode 的原问题以外，我还给介绍了两个「进阶」问题。
在「进阶一」输出方案问题中，我给你介绍了如何使用「一维数组」存储「二维信息」，这是一个常见的手段。以及如何通过问题等价变换来降低编码难度。
通过「进阶二」我向你展示了，同一道题换了一个前提条件，求解方法将截然不同。
改了一个前提条件之后，原本的解法对应的证明将会失效，原本的算法也就不能正确求解了。
类似的问题我在 路径问题 第一讲 的「思考」中也问过。
这就是我们做算法题一定要讲「证明」的原因，搞清楚本质了才是真正会做。
路径问题（目录）
62.不同路径（中等）：路径问题第一讲
63.不同路径 II（中等）：路径问题第二讲
64.最小路径和（中等）：（本篇）
120.三角形最小路径和（中等）
931.下降路径最小和（中等）
1289.下降路径最小和 II（困难）
1575.统计所有可行路径（困难）
576.出界的路径数（中等）
1301.最大得分的路径数目（困难）
欢迎补充 ~
最后
这是我们「刷穿 LeetCode」系列文章的第 No.64 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
