文章起笔:2021年11月13日16:28:08
问题描述及示例
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我的题解(动态规划)
有关动态规划的思路总结,之前写过一个相关的题解博客:
参考:【算法-LeetCode】53. 最大子序和(动态规划初体验)_赖念安的博客-CSDN博客
里面也有我写的其他动态规划题解,一些通用的步骤都是一样的,也可以作为参考,进行对照思考。
而本题的思路和我之前做的一个动态规划题目非常像:
参考:【算法-LeetCode】64. 最小路径和(动态规划;二维数组;滚动数组)_赖念安的博客-CSDN博客
两道题目都有共同的特点:dp[i][j]
的值都是由其相邻的正上方元素(dp[i-1][j]
)和相邻的正左方元素(dp[i][j-1]
)决定的。所以两者的动态转移方程也有相似之处。
此前我也做过另一道路径问题,可供参考:
参考:【算法-LeetCode】62. 不同路径(动态规划;滚动数组)_赖念安的博客-CSDN博客
本题的思路和上面的思路是一样的,唯一不同的就是本题需要对障碍物做一点判断。
我的题解1(二维dp数组)
在本题中,dp[i][j]
代表由起点(也就是点 [0,0]
)到点 [i][j]
有几条可行的路径(当然,按照题目要求只能向下或想右走)。
具体的分析步骤就不赘述了,和上面那道题的基本一样,只要根据我之前总结的那几个步骤一点点分析即可。说一下本题的总体核心思路:我们要走到点 [i][j]
,只能先到达其正上方或者正左方,所以只要知道到达 [i-1][j]
和 [i][j-1]
各有几条符合条件的路径,再将两者相加即可得到到达 [i][j]
总共有几条路径。
但是要注意在遍历过程中对障碍物做一点额外的判断。如果当前遍历的 obstacleGrid
元素为障碍物,那么就可以直接将该相应位置的 dp
元素置为 0
。
而且在本题中,我所创建的 dp
数组的长宽相比较于 obstacleGrid
是增加了一行一列的。这增加的一行一列就相当于是辅助用的行和列,它们的初始值都是 0
。
详细解释请看下方注释:
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
// 注意 dp 数组的长宽都比 obstacleGrid 大 1
let dp = new Array(obstacleGrid.length + 1).fill(0).map(
// 注意这里我把 dp 数组元素的值都初始化为0,此前我是初始化为1
() => new Array(obstacleGrid[0].length + 1).fill(0)
);
// dp 数组的首行和首列应该被初始化为0,上面创建dp数组的时候就相当于同时完成了初始化
// 开始遍历obstacleGrid数组,同时填充dp数组
for(let i = 1; i < dp.length; i++) {
for(let j = 1; j < dp[0].length; j++) {
// 如果当前遍历的 obstacleGrid 元素为障碍物,则直接让相应的 dp 数组元素为 0
// 代表到达该位置的路径总条数为 0,注意该判断应当在下面那个判断前以应对[[1]]的情况
if(obstacleGrid[i-1][j-1] === 1) {
dp[i][j] = 0;
continue;
}
// 注意要对 dp[1][1] 这个元素做特殊处理
if(i === 1 && j === 1) {
dp[i][j] = 1;
continue;
}
// 剩下的元素的填充逻辑就和之前那道题目是一样的了
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
return dp[dp.length-1][dp[0].length-1];
};
提交记录
执行结果:通过
41 / 41 个通过测试用例
执行用时:88 ms, 在所有 JavaScript 提交中击败了15.78%的用户
内存消耗:38.9 MB, 在所有 JavaScript 提交中击败了31.70%的用户
时间:2021/11/13 16:34
我的题解2(一维dp数组)
这里用到的“滚动数组”的思路也和上面提到的博客里的思路是一样的,所以就不再赘述了。
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
// 创建dp数组,注意其长度比obstacleGrid的长度大1,
// 前面多出来的那个位置(即dp[0])是辅助位,同时dp数组中的元素都被初始化为 0
let dp = new Array(obstacleGrid[0].length + 1).fill(0);
// 注意要特意初始化dp[1]这个元素,否则就会影响后续元素的计算
dp[1] = obstacleGrid[0][0] ? 0 : 1;
// 下面的逻辑没有太大的变化,只不过把原来二维dp数组解法里针对dp[1][1]的操作提到了上面
for(let i = 0; i < obstacleGrid.length; i++) {
for(let j = 0; j < obstacleGrid[0].length; j++) {
if(obstacleGrid[i][j] === 1) {
dp[j+1] = 0;
continue;
}
dp[j+1] = dp[j+1] + dp[j];
}
}
return dp[dp.length-1];
};
提交记录
执行结果:通过
41 / 41 个通过测试用例
执行用时:72 ms, 在所有 JavaScript 提交中击败了75.27%的用户
内存消耗:38.2 MB, 在所有 JavaScript 提交中击败了87.77%的用户
时间:2021/11/13 17:09
可以看到,使用一维 dp
数组的时间和空间性能都显著提升了。但是其核心的思路还是不变的,只不过是重复利用了某一个一维数组。而我们可以重复利用这个数组的最关键因素就是:除了需要初始化的那些 dp
元素,其余所有的 dp[i][j]
都是通过其“前面”的元素计算得到的,或者说新的 dp[i][j]
会覆盖前一轮计算得到的 dp[i][j]
,所以一维数组中的某一个位置能够被重复利用。
基本上所有的二维 dp
数组都可以通过上面的思路化为一维数组。所以我觉得在研究一维 dp
数组(滚动数组)前,应该先对二维的实现原理有充分的理解。
官方题解
更新:2021年7月29日18:43:21
因为我考虑到著作权归属问题,所以【官方题解】部分我不再粘贴具体的代码了,可到下方的链接中查看。
更新:2021年11月13日16:36:03
参考:不同路径 II - 不同路径 II - 力扣(LeetCode)
【更新结束】
有关参考
更新:2021年11月13日16:36:47
参考:【算法-LeetCode】62. 不同路径(动态规划;滚动数组)_赖念安的博客-CSDN博客
更新:2021年9月22日14:08:16
参考:【算法-LeetCode】53. 最大子序和(动态规划初体验)_赖念安的博客-CSDN博客
更新:2021年9月23日22:15:04
参考:【算法-LeetCode】64. 最小路径和(动态规划;二维数组;滚动数组)_赖念安的博客-CSDN博客
参考:【算法-LeetCode】322. 零钱兑换(动态规划;博采众长的完全背包问题详解;二维数组;滚动数组)_赖念安的博客-CSDN博客