长春做网站新格公司,网页设计教程软件,做有奖竞猜网站违法吗,常州市钟楼建设局网站目录
一、#xff08;leetcode 62#xff09;不同路径
1.动态规划
1#xff09;确定dp数组#xff08;dp table#xff09;以及下标的含义
2#xff09;确定递推公式
3#xff09;dp数组的初始化
4#xff09;确定遍历顺序
5#xff09;举例推导dp数组 2.数论方…目录
一、leetcode 62不同路径
1.动态规划
1确定dp数组dp table以及下标的含义
2确定递推公式
3dp数组的初始化
4确定遍历顺序
5举例推导dp数组 2.数论方法
二、leetcode 63不同路径 II 一、leetcode 62不同路径
力扣题目链接
1.动态规划
机器人从(0 , 0) 位置出发到(m - 1, n - 1)终点。
按照动规五部曲来分析
1确定dp数组dp table以及下标的含义
dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径。
2确定递推公式
想要求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]只有这两个方向过来。
3dp数组的初始化
首先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;4确定遍历顺序
这里要看一下递推公式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]一定是有数值的。
5举例推导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) 2.数论方法
在这个图中可以看出一共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)
二、leetcode 63不同路径 II
力扣题目链接
有障碍的话其实就是标记对应的dp tabledp数组保持初始值(0)就可以了
动规五部曲
1确定dp数组dp table以及下标的含义
dp[i][j] 表示从0 0出发到(i, j) 有dp[i][j]条不同的路径。
2确定递推公式
递推公式和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];
}3dp数组如何初始化
在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]同理
4确定遍历顺序
从递归公式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];}
}5举例推导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)
