63. 不同路径 II
63. 不同路径 II
题目
You are given an m x n
integer array grid
. There is a robot initially located at the top-left corner (i.e., grid[0][0]
). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]
). The robot can only move either down or right at any point in time.
An obstacle and space are marked as 1
or 0
respectively in grid
. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 10^9
.
Example 1:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
Right -> Right -> Down -> Down
Down -> Down -> Right -> Right
Example 2:
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Constraints:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j]
is0
or1
.
题目大意
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
解题思路
- 这一题是 第 62 题 的加强版。也是一道考察 DP 的简单题。
- 这一题比第 62 题增加的条件是地图中会出现障碍物,障碍物的处理方法是
dp[i][j]=0
。 - 需要注意的一种情况是,起点就是障碍物,那么这种情况直接输出 0 。
❤️ | 1 | 1 | 1 | 1 | 1 | 1 |
---|---|---|---|---|---|---|
1 | 💩 | 1 | 2 | 💩 | 1 | 2 |
1 | 1 | 2 | 4 | 4 | 5 | 7 |
思路一:DP-压缩状态
复杂度分析
- 时间复杂度:
O(m * n)
,遍历整个二维数组。 - 空间复杂度:
O(m)
,使用了一个长度为m
的arr
数组来存储中间状态。
思路一:DP-压缩状态
复杂度分析
- 时间复杂度:
O(m * n)
,遍历整个二维数组。 - 空间复杂度:
O(1)
,由于obstacleGrid[i][j]
只与obstacleGrid[i-1][j]
及obstacleGrid[i][j-1]
有关,所以可以直接原地修改obstacleGrid
数组。
代码
// 时间复杂度 O(nm),空间复杂度 O(m)
const path = (inputArr) => {
// 如果起点就是障碍物
if (inputArr[0][0] === 1) return 0;
const m = inputArr.length;
const n = inputArr[0].length;
// 用0填充,因为现在有障碍物
let arr = new Array(m).fill(0);
// 第一列先写成1
arr[0] = 1;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (inputArr[j][i] === 1) {
// 遇到障碍物arr[j]就变成0,这里包含了第一列的情况
arr[j] = 0;
} else if (j > 0) {
arr[j] = arr[j - 1] + arr[j];
}
}
}
return arr[m - 1];
};
// 时间复杂度 O(nm),空间复杂度 O(1)
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function (obstacleGrid) {
const m = obstacleGrid.length,
n = obstacleGrid[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// 遇到障碍物 obstacleGrid[i][j] 就变成 0
if (obstacleGrid[i][j] == 1) {
obstacleGrid[i][j] = 0;
continue;
}
// 起点
if (i == 0 && j == 0) {
obstacleGrid[i][j] = 1;
}
// 第一行
else if (i == 0) {
obstacleGrid[i][j] = obstacleGrid[i][j - 1];
}
// 第一列
else if (j == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j];
} else {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
}
}
return obstacleGrid[m - 1][n - 1];
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
62 | 不同路径 | [✓] | 数学 动态规划 组合数学 | |
980 | 不同路径 III | 位运算 数组 回溯 1+ | ||
2304 | 网格中的最小路径代价 | 数组 动态规划 矩阵 | ||
2435 | 矩阵中和能被 K 整除的路径 | 数组 动态规划 矩阵 |