【动态规划/路径问题】进阶「最小路径和」问题 ...
前言
今天是我们讲解「动态规划专题」中的 路径问题 的第三天。
我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。
路径问题 我按照编排好的顺序进行讲解（一天一道）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 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];
}
}
- 时间复杂度：
- 空间复杂度：
进阶
- 如果要输出总和最低的路径呢？（如果有多个答案，返回其中之一即可）
从原问题我们知道，我们需要从 (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 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
