动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i][j] 的含义为 达到网格 i、j 处共有 dp[i][j] 条不同的路径；
确定递推公式：
- 当 dp[i][j] 处不是障碍时：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]；- 当 dp[i][j] 处是障碍时：
dp[i][j] = 0；如何初始化 dp 数组：第一列、第一行初始化为 1；
确定遍历顺序：根据递推公式得知，需要从前向后遍历；
举例推导 dp 数组：
复杂度
-
时间复杂度：
O(M * N)； -
空间复杂度：
O(M * N)；
代码实现
var uniquePathsWithObstacles = function (obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
// 1. m*n 的矩阵
const dp = new Array(m).fill('').map(i => new Array(n).fill(0));
// 2. 初始化 dp 数组，第一行、第一列都赋值为 1，遇到障碍物后面则不再更新，都是 0
for (let i = 0; i < m && obstacleGrid[i][0] === 0; ++i) dp[i][0] = 1;
for (let i = 0; i < n && obstacleGrid[0][i] === 0; ++i) dp[0][i] = 1;
// 3. 根据递推公式，更新矩阵 dp[i][j] 的值
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// 如果当前格子是障碍物，dp[i][j] = 0，否则返回 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
动态规划（状态压缩）
解题思路
由于 dp[i][j] 仅与第 i 行和第 i − 1 行的状态有关，因此可以使用滚动数组代替代码中的二维数组，则递推公式改成
dp[j] = dp[j] + dp[j - 1]；具体的递推过程如下：
复杂度
-
时间复杂度：
O(M * N)； -
空间复杂度：
O(N)；
代码实现
??被称为非空运算符，用来判断是否是 null / undefined；
var uniquePathsWithObstacles = function (obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
// 1. obstacleGrid 作为 dp 滚动数组
// 2. 根据递推公式，更新矩阵 dp[i][j] 的值
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (obstacleGrid[i][j] === 0) {
// 不是障碍物
if (i === 0) {
// 取左边的值
obstacleGrid[i][j] = obstacleGrid[i][j - 1] ?? 1;
} else if (j === 0) {
// 取上边的值
obstacleGrid[i][j] = obstacleGrid[i - 1][j] ?? 1;
} else {
// 取左边和上边的和
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
} else {
// 如果是障碍物，则路径为 0
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[m - 1][n - 1];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 62. 不同路径
上一篇
评论
