大型网站 建设意义,赚钱一天赚300到500平台,家用云做网站,网站开发广告宣传本文章代码以c为例#xff01;
一、力扣第62题#xff1a;不同路径
题目#xff1a;
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;…本文章代码以c为例
一、力扣第62题不同路径
题目
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
示例 1 输入m 3, n 7
输出28
示例 2
输入m 3, n 2
输出3
解释
从左上角开始总共有 3 条路径可以到达右下角。
1. 向右 - 向下 - 向下
2. 向下 - 向下 - 向右
3. 向下 - 向右 - 向下示例 3
输入m 7, n 3
输出28示例 4
输入m 3, n 3
输出6
提示
1 m, n 100题目数据保证答案小于等于 2 * 109
思路
# 深搜
这道题目刚一看最直观的想法就是用图论里的深搜来枚举出来有多少种路径。
注意题目中说机器人每次只能向下或者向右移动一步那么其实机器人走过的路径可以抽象为一棵二叉树而叶子节点就是终点
如图举例 此时问题就可以转化为求二叉树叶子节点的个数代码如下
class Solution {
private:int dfs(int i, int j, int m, int n) {if (i m || j n) return 0; // 越界了if (i m j n) return 1; // 找到一种方法相当于找到了叶子节点return dfs(i 1, j, m, n) dfs(i, j 1, m, n);}
public:int uniquePaths(int m, int n) {return dfs(1, 1, m, n);}
};大家如果提交了代码就会发现超时了
来分析一下时间复杂度这个深搜的算法其实就是要遍历整个二叉树。
这棵树的深度其实就是mn-1深度按从1开始计算。
那二叉树的节点个数就是 2^(m n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树其实没有遍历整个满二叉树只是近似而已
所以上面深搜代码的时间复杂度为O(2^(m n - 1) - 1)可以看出这是指数级别的时间复杂度是非常大的。
# 动态规划
机器人从(0 , 0) 位置出发到(m - 1, n - 1)终点。
按照动规五部曲来分析
确定dp数组dp table以及下标的含义
dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径。
确定递推公式
想要求dp[i][j]只能有两个方向来推导出来即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥是从(0, 0)的位置到(i - 1, j)有几条路径dp[i][j - 1]同理。
那么很自然dp[i][j] dp[i - 1][j] dp[i][j - 1]因为dp[i][j]只有这两个方向过来。
dp数组的初始化
如何初始化呢首先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;确定遍历顺序
这里要看一下递推公式dp[i][j] dp[i - 1][j] dp[i][j - 1]dp[i][j]都是从其上方和左方推导而来那么从左到右一层一层遍历就可以了。
这样就可以保证推导dp[i][j]的时候dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
举例推导dp数组
如图所示 以上动规五部曲分析完毕C代码如下
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(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) {vectorint 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];}
};时间复杂度O(m × n)空间复杂度O(n)
# 数论方法
在这个图中可以看出一共mn的话无论怎么走走到终点都需要 m n - 2 步。 在这m n - 2 步中一定有 m - 1 步是要向下走的不用管什么时候向下走。
那么有几种走法呢 可以转化为给你m n - 2个不同的数随便取m - 1个数有几种取法。
那么这就是一个组合问题了。
那么答案如图所示 求组合的时候要防止两个int相乘溢出 所以不能把算式的分子都算出来分母都算出来再做除法。
例如如下代码是不行的。
class Solution {
public:int uniquePaths(int m, int n) {int numerator 1, denominator 1;int count m - 1;int t m n - 2;while (count--) numerator * (t--); // 计算分子此时分子就会溢出for (int i 1; i m - 1; i) denominator * i; // 计算分母return numerator / denominator;}
};
需要在计算分子的时候不断除以分母代码如下
class Solution {
public:int uniquePaths(int m, int n) {long long numerator 1; // 分子int denominator m - 1; // 分母int count m - 1;int t m n - 2;while (count--) {numerator * (t--);while (denominator ! 0 numerator % denominator 0) {numerator / denominator;denominator--;}}return numerator;}
};时间复杂度O(m)空间复杂度O(1)
计算组合问题的代码还是有难度的特别是处理溢出的情况
# 总结
本文分别给出了深搜动规数论三种方法。
深搜当然是超时了顺便分析了一下使用深搜的时间复杂度就可以看出为什么超时了。
然后在给出动规的方法依然是使用动规五部曲这次我们就要考虑如何正确的初始化了初始化和遍历顺序其实也很重要
二、力扣第63题不同路径 II
题目
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示。 示例 1 输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]]
输出2
解释3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径
1. 向右 - 向右 - 向下 - 向下
2. 向下 - 向下 - 向右 - 向右示例 2 输入obstacleGrid [[0,1],[0,0]]
输出1提示
m obstacleGrid.lengthn obstacleGrid[i].length1 m, n 100obstacleGrid[i][j] 为 0 或 1
思路
这道题相对于62.不同路径
(opens new window) 就是有了障碍。
第一次接触这种题目的同学可能会有点懵这有障碍了应该怎么算呢
62.不同路径
(opens new window)中我们已经详细分析了没有障碍的情况有障碍的话其实就是标记对应的dp tabledp数组保持初始值(0)就可以了。
动规五部曲
确定dp数组dp table以及下标的含义
dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径。
确定递推公式
递推公式和62.不同路径一样dp[i][j] dp[i - 1][j] dp[i][j - 1]。
但这里需要注意一点因为有了障碍(i, j)如果就是障碍的话应该就保持初始状态初始状态为0。
所以代码为
if (obstacleGrid[i][j] 0) { // 当(i, j)没有障碍的时候再推导dp[i][j]dp[i][j] dp[i - 1][j] dp[i][j - 1];
}dp数组如何初始化
在62.不同路径
(opens new window)不同路径中我们给出如下的初始化
vectorvectorint dp(m, vectorint(n, 0)); // 初始值为0
for (int i 0; i m; i) dp[i][0] 1;
for (int j 0; j n; j) dp[0][j] 1;因为从(0, 0)的位置到(i, 0)的路径只有一条所以dp[i][0]一定为1dp[0][j]也同理。
但如果(i, 0) 这条边有了障碍之后障碍之后包括障碍都是走不到的位置了所以障碍之后的dp[i][0]应该还是初始值0。
如图 下标(0, j)的初始化情况同理。
所以本题初始化代码为
vectorvectorint dp(m, vectorint(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循环的终止条件一旦遇到obstacleGrid[i][0] 1的情况就停止dp[i][0]的赋值1的操作dp[0][j]同理
确定遍历顺序
从递归公式dp[i][j] dp[i - 1][j] dp[i][j - 1] 中可以看出一定是从左到右一层一层遍历这样保证推导dp[i][j]的时候dp[i - 1][j] 和 dp[i][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数组
拿示例1来举例如题 对应的dp table 如图 如果这个图看不懂建议再理解一下递归公式然后照着文章中说的遍历顺序自己推导一下
动规五部分分析完毕对应C代码如下
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] 1 || obstacleGrid[0][0] 1) //如果在起点或终点出现了障碍直接返回0return 0;vectorvectorint dp(m, vectorint(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(vectorvectorint obstacleGrid) {if (obstacleGrid[0][0] 1)return 0;vectorint 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();}
};时间复杂度O(n × m)n、m 分别为obstacleGrid 长度和宽度空间复杂度O(m)
# 总结
本题是62.不同路径
(opens new window)的障碍版整体思路大体一致。
但就算是做过62.不同路径在做本题也会有感觉遇到障碍无从下手。
其实只要考虑到遇到障碍dp[i][j]保持0就可以了。
也有一些小细节例如初始化的部分很容易忽略了障碍之后应该都是0的情况。 day39补
