leetcode 63. 不同路径 II
不同路径的解法合集
记忆化递归
- 如果是没有障碍物的话，从(0,0)出发，每次只能往下走、或者往右走。假设i表示行、j表示列，当前点为(i,j)，那么每次只能往(i + 1, j)移动、或者往(i, j + 1)移动。
- 对于有障碍物的情况下怎么办呢？ 其实也简单，直接返回0就可以了，这表能走到障碍物的路径总和为0。
- 有了上述条件，递归就很容易写了，每次往右、或者往下走。
- 到达边界条件返回0，到达终点返回1。
- 上图中橙色的(2,2)这个点，表示从这里发出到达终点有多少路径。
- 同理，(0,0)就是从起点出发，走到终点有多少路径，也就是题目的要求。
注意，纯递归是不行的，因为有大量的重复计算，需要加个缓存。
class Solution {
map<pair<int,int>, int> map;//用来保存计算结果
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
if (obstacleGrid[0][0] == 1)//起点有障碍物，那么直接返回0
return 0;
if (obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1] == 1)//终点存在障碍物
return 0;
return dfs(obstacleGrid, 0, 0);
}
int dfs(vector<vector<int>>& obstacleGrid, int i, int j)
{
//如果到达当前点的走法总数已经算出，那么直接返回
if (map.find({ i,j }) != map.end())
return map[{i, j}];
//越界检查和障碍物检查
if (i >= obstacleGrid.size() || j >= obstacleGrid[0].size() || obstacleGrid[i][j] == 1)
return 0;
//到达左下角，返回1
if (i == obstacleGrid.size() - 1 && j == obstacleGrid[0].size() - 1)
return 1;
//到达当前点的走法
map[{i, j}] =dfs(obstacleGrid, i+1, j) + dfs(obstacleGrid, i, j+1);
return map[{i, j}];
}
};
动态规划—起点到终点
- 对于动态规划，我们可以反过来想。 如何到达下图中橙色的(1,2)这个点。
- 只能由两个方向而来，上方、或者是左方；对于(3,2)障碍物这个点来说，能到达这里的路径就是0。 所以对于(i,j)这个点来说，其动态规划转移方程就是：
if 当前点不是障碍物：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
else:
dp[i][j] = 0- 我们还需要处理下边界情况，也就是第一列、第一行时
- 如上图，只要第一列中的某个格子是障碍物，那么这个格子跟后面的都无法到达。
- 同理，第一行中如果有格子是障碍物，那么这个格子跟后面的都无法到达了。
- 时间复杂度：O(M * N)
- 空间复杂度：O(M * N)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
if (obstacleGrid[0][0] == 1) return 0;
int r = obstacleGrid.size();
int c = obstacleGrid[0].size();
if (obstacleGrid[r - 1][c - 1] == 1) return 0;
vector<vector<int>> dp(r, vector<int>(c));
dp[0][0] = 1;
//处理第一列
for (int i = 1; i < r; ++i)
{
//当前格子有障碍或者当前格子所处列有障碍物
if (obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0)
{
dp[i][0] = 0;
}
else
{
dp[i][0] = 1;
}
}
//处理第一行
for (int j = 1; j < c; j++)
{
if (obstacleGrid[0][j] == 1 || dp[0][j - 1] == 0)
{
dp[0][j] = 0;
}
else
{
dp[0][j] = 1;
}
}
for (int i = 1; i < r; i++)
{
for (int j = 1; j < c; j++)
{
//当前格子存在障碍物
if (obstacleGrid[i][j] == 1)
dp[i][j] = 0;
else//路径总数来自于上方(dp[i-1][j])和左方(dp[i][j-1])
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[r - 1][c - 1];
}
};
动态规划—终点到起点
- 跟【动态规划-1】解法正好是反过来的，【动态规划-1】解法中，是从(0,0)走到(n-1,m-1)。
- 【动态规划-2】中，是从(n-1,m-1)走到(0,0)。
- 所以我们反过来推导，对于(2,2)这个点，只能从下方、右方转移过来。
同样，反着推的时候也需要处理下边界问题，也就是最后一行，最后一列需要单独处理一下。这里的思路跟前一种解法是一样的，只是倒退来的。
时间复杂度：O(M * N) 空间复杂度：O(M * N)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
if (obstacleGrid[0][0] == 1) return 0;
int r = obstacleGrid.size();
int c = obstacleGrid[0].size();
if (obstacleGrid[r - 1][c - 1] == 1) return 0;
vector<vector<long>> dp(r, vector<long>(c));
//最小子结果
dp[r - 1][c - 1] = 1;
//处理第一列
for (int i = r - 2; i >= 0; --i)
{
//当前格子有障碍或者当前格子所处列有障碍物
if (obstacleGrid[i][c - 1] == 1 || dp[i+1][c - 1] == 0)
{
dp[i][c - 1] = 0;
}
else
{
dp[i][c - 1] = 1;
}
}
//处理第一行
for (int j = c - 2; j >= 0; --j)
{
if (obstacleGrid[r - 1][j] == 1 || dp[r - 1][j+1] == 0)
{
dp[r - 1][j] = 0;
}
else
{
dp[r - 1][j] = 1;
}
}
for (int i = r - 2; i >= 0; i--)
{
for (int j = c - 2; j >= 0; j--)
{
//当前格子存在障碍物
if (obstacleGrid[i][j] == 1)
dp[i][j] = 0;
else//路径总数来自于上方(dp[i-1][j])和左方(dp[i][j-1])
dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
}
}
return dp[0][0];
}
};
动态规划+空间优化
- 对于动态规划的两种解法，都是只需要上一层的解，而不需要上上一层的。`
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]- 也就是求第i行时，只需要i-1行已求解过的值，不需要i-2行的了。
- 所以这里可以用滚动数组进行优化，将二维数组改为一维数组。
- 一维数组的大小为列的长度。
- 第三次迭代时，求第三个格子6时，由于左边的值已经是已知的，第二次迭代时同位置的值也是已知的。所以当前值的计算方式就是：
- 这里是把地图一行一行的看，一行一行的求解，求解当前行只要确保上一行已经求出来即可
- 因此这里的一位数组的大小就是列的长度，相当于每求解新的一行，是从新的一行的第一个元素开始求解。
- 但注意这里还用到了滚动数组的思想，即当前列对应上一行的该列元素就是当前列还未被替换的元素
- 因为用到了滚动数组，那么这里的最小子问题就成了第一行第一列的第一个元素
计算当前值 = 以求出的左边值 + 上一次迭代同位置的值
dp[j] = dp[j - 1] + dp[j]时间复杂度：O(M * N) 空间复杂度：O(M)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
if (obstacleGrid[0][0] == 1) return 0;
int r = obstacleGrid.size();
int c = obstacleGrid[0].size();
if (obstacleGrid[r - 1][c - 1] == 1) return 0;
vector<int> dp(c);
//这里滚动数组的第一个元素，即每一行的第一个元素，只要当前格子没有障碍物，就都是1
dp[0] = 1;
for (int i = 0; i<r; i++)
{
for (int j = 0; j <c; j++)
{
//有障碍物的格子直接赋0
if (obstacleGrid[i][j] == 1)
dp[j] = 0;
//否则dp[j]的值由左方和上一次迭代的dp[j]累加而来
else if (obstacleGrid[i][j] == 0 && j - 1 >=0)
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[c-1];
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/05/08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号