今天是我们讲解「动态规划专题」中的 路径问题 的第二天。
今天讲解的题目主要是为了巩固 上一讲 我和你分享的 DP 分析技巧。
另外,我在文章结尾处列举了我所整理的关于 路径问题 的相关题目。
路径问题 我按照编排好的顺序进行讲解(一天一道)。
你也先可以尝试做做,也欢迎你向我留言补充,你觉得与路径相关的 DP 类型题目 ~
这是 LeetCode 上的「63. 不同路径 II」,难度为 Medium。
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示:
这道题和 62. 不同路径 相比,不能说完全相同,只能说一模一样 ~
多了某些格子有障碍物(不可达)的限制,但丝毫不影响我们的分析。
还是定义 f[i][j]
为到达位置 (i,j)
的不同路径数量。
那么 f[n-1][m-1]
就是我们最终的答案。
f[0][0] = 1
是一个显而易见的起始条件,同时由于某些格子上有障碍物,对于 grid[i][j]==1
的格子,则有 f[i][j] = 0
。
由于题目限定了我们只能 往下 或者 往右 移动,因此我们按照「当前可选方向」进行分析:
f[i][j] = f[i-1][j]
f[i][j] = f[i][j-1]
f[i][j] = f[i][j-1] + f[i-1][j]
代码:
class Solution {
public int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] f = new int[m][n];
f[0][0] = grid[0][0] == 1 ? 0 : 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) {
if (i > 0 && j > 0) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
} else if (i > 0) {
f[i][j] = f[i - 1][j];
} else if (j > 0) {
f[i][j] = f[i][j - 1];
}
}
}
}
return f[m - 1][n - 1];
}
}
今天这道题目没有太多的「亮点」,就是单纯是 62. 不同路径 的修改篇。
但我仍然建议你打开 LeetCode 重新做一遍,并结合我上一讲提到过的分析技巧。
62.不同路径(中等):路径问题第一讲
63.不同路径 II(中等):(本篇)
64.最小路径和(中等)
120.三角形最小路径和(中等)
931.下降路径最小和(中等)
1289.下降路径最小和 II(困难)
1575.统计所有可行路径(困难)
576.出界的路径数(中等)
1301.最大得分的路径数目(困难)
欢迎补充 ~
这是我们「刷穿 LeetCode」系列文章的第 No.63
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。