本文主要是介绍代码随想录算法训练营DAY39|C++动态规划Part.2|62.不同路径、63.不同路径II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 62.不同路径
- 思路
- dp含义
- 递推公式
- 初始化
- 遍历顺序
- 打印
- CPP代码
- 63.不同路径II
- 思路
- dp含义
- 递推公式
- 初始化
- 遍历
- 打印
- CPP代码
- 经典错误
62.不同路径
力扣题目链接
文章讲解:62.不同路径
视频讲解:动态规划中如何初始化很重要!| LeetCode:62.不同路径
状态: 本题还是比较简单的,无论是初始化还是dp数组的确定难度都不高
本题其实可以用深度优先搜索,但是那会超时。时间复杂度为 O ( 2 ( m + n − 1 ) − 1 ) O(2^{(m + n - 1)} - 1) O(2(m+n−1)−1)
思路
dp含义
给定的题目是二维的一个地图,所以我们的dp数组肯定也得是一个二维的。
求得也是从起始位置(0, 0)
到终止位置end(i, j)
有多少种不同的路径。
dp[i][j]
:表示从(0, 0)
出发,到(i, j)
有dp[i][j]
条不同的路径。
递推公式
对于某一个格子d[i][j]
只有两种走法能到达,从dp[i-1][j]
往右走和dp[i][j-1]
往下走。
所以:dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化
首先dp[i][0]
一定都是1,因为从(0, 0)
的位置到(i, 0)
的路径只有一条,那么dp[0][j]
也同理。
如果我们不把最上面一行和最左面一列的位置进行初始化 ,其他格子的路径和是无法推导的。如图所示:
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
遍历顺序
遍历顺序就是很直观的:
从左往右遍历,从上往下遍历
打印
错误的话就打印出来Debug
如果不符合预期直接看看到底哪里出了问题
CPP代码
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m; i++) dp[i][0] = 1;for (int j = 0; j < n; j++) dp[0][j] = 1;for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};
- 时间复杂度:O(m × n)
- 空间复杂度:O(m × n)
滚动数组的方法,可以优化点空间,建议先理解了二维,在理解一维,C++代码如下:
class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n);for (int i = 0; i < n; i++) dp[i] = 1;for (int j = 1; j < m; j++) {for (int i = 1; i < n; i++) {dp[i] += dp[i - 1];}}return dp[n - 1];}
};
63.不同路径II
力扣题目链接
文章讲解:63.不同路径II
视频讲解:动态规划,这次遇到障碍了| LeetCode:63. 不同路径 II
状态:个人做的时候,障碍的情况也太多了,难道要一个一个讨论吗?
答案显然不是,所以写代码还是有讲究的
与上题的区别:在整个路径中多了障碍
思路
dp含义
同上62.不同路径
递推公式
同上62.不同路径
但是由于障碍的存在,比如第[i][j]
的位置有障碍,那么我们的公式:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
不需要推导,因为我们走不了这一步。
这里我们就添加一个条件:
if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候,再推导dp[i][j]dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
初始化
与上一题中有相同也有不同,因为从(0, 0)
的位置到(i, 0)
的路径只有一条,所以dp[i][0]
一定为1,dp[0][j]
也同理。
但是一定要注意障碍物在初始化边上的情况。
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
遍历
老规矩,还是从左到右一层层遍历。
for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}
}
打印
打印观察dp数组,如果原图是这样的:
dp数组如图:
CPP代码
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍,直接返回0return 0;vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};
- 时间复杂度:O(n × m),n、m 分别为obstacleGrid 长度和宽度
- 空间复杂度:O(n × m)
优化空间的版本
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if (obstacleGrid[0][0] == 1)return 0;vector<int> dp(obstacleGrid[0].size());for (int j = 0; j < dp.size(); ++j)if (obstacleGrid[0][j] == 1)dp[j] = 0;else if (j == 0)dp[j] = 1;elsedp[j] = dp[j-1];for (int i = 1; i < obstacleGrid.size(); ++i)for (int j = 0; j < dp.size(); ++j){if (obstacleGrid[i][j] == 1)dp[j] = 0;else if (j != 0)dp[j] = dp[j] + dp[j-1];}return dp.back();}
};
经典错误
在这里贴一段我的错误代码:
典型的补墙行为,而且还无法处理障碍物封路的情况。
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(); //rowint n = obstacleGrid[0].size(); //columnif (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) return 0;vector<vector<int>> dp(m, vector(n, 0));for (int i = 0; i < m; ++i) {if (!(obstacleGrid[i][0] == 1))dp[i][0] = 1;}for (int j = 0; j < n; ++j) {if (!(obstacleGrid[0][j] == 1))dp[0][j] = 1;}for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {if (obstacleGrid[i][j - 1] == 1) {dp[i][j] = dp[i - 1][j];continue;}if (obstacleGrid[i - 1][j] == 1) {dp[i][j] = dp[i][j - 1];continue;}dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
这篇关于代码随想录算法训练营DAY39|C++动态规划Part.2|62.不同路径、63.不同路径II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!