题目:62.不同路径 63.不同路径II 343.整数拆分 96.不同的二叉搜索树
需要重做:63 343 96
62.不同路径
思路:
法1:动规
五部曲:
1.含义:dp[i][j]:从(0,0)出发到(i,j),有多少条路径
2.递推:dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
3.初始化:第0行和列,除了(0,0),都是1.
4.遍历顺序:因为递推式需要左或者上的,所以只要这两个有就行,选择从左到右一层一层即可
注意:优化:只使用一维数组,因为需要左边的和上面的,所以可以只用一行,这个元素+=左边的元素即可,代码2即为优化后的。
代码1:
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>dp(m,vector<int>(n,0));//初始化for(int i=0;i<n;i++){dp[0][i]=1;}for(int i=0;i<m;i++){dp[i][0]=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];}
};
代码2:
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];}
};
法2:dfs(超时了),因为树高m+n-1,复杂度是2的m+n-1次方
代码:
class Solution {
public: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);}int uniquePaths(int m, int n) {return dfs(1,1,m,n);}
};
法3:数论:
思路:共有m+n-2步,在这些步骤中选m-1步向下走即可。即C下面(m+n-2)上面(m-1)
代码:注意不能先算分子再算分母再除,会溢出,选择边算边除
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;}
};
63. 不同路径 II
思路:现在有障碍了,就在dp数组里面加个条件即可
五部曲:
1.含义:dp[i][j]。到达i,j有几条路线
2.递推式:dp[i][j]=dp[i-1][j]+dp[i][j-1]
3.初始化:0行0列都是1,如果0行0列中有石头,则:行的话,在石头右边及石头的都为0,列的话石头及石头下面都是0.
4.遍历顺序:左到右,一层一层
注意:初始化的时候,如果有障碍物了,后面的都要为0!因为过不去!
代码:
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size();int n=obstacleGrid[0].size();vector<vector<int>>dp(m,vector<int>(n,0));//如果障碍在开始或者终点,直接returnif(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1)return 0;//初始化for(int i=0;i<n&&obstacleGrid[0][i]!=1;i++){dp[0][i]=1;}for(int i=0;i<m&&obstacleGrid[i][0]!=1;i++){dp[i][0]=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];}
};
343.整数拆分 (可跳过)
思路:本来想着拆成根号然后按照余数来分,但是发现测试了发现不行,考虑动规。
五部曲:
1.dp[i],为i的时候拆的乘积最大是多少
2.dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j))。含义:最大值等于max(当前这个的最大值,i-j的乘积最大值*j,和i-j*j的最大值)
3.0,1无含义,dp[2]=1
4.遍历方向:i从3开始,j从1开始到i/2
注意:因为拆分一个数n 使之乘积最大,那么一定是拆分成m个近似相同的子数相乘才是最大的。所以j到i/2就可以了
代码:
class Solution {
public:int integerBreak(int n) {vector<int>dp(n+1);dp[2]=1;for(int i=3;i<=n;i++){for(int j=1;j<=i/2;j++){dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));}}return dp[n];}
};
法2:贪心:
代码:本题也可以用贪心,每次拆成n个3,如果剩下是4,则保留4,然后相乘,但是这个结论需要数学证明其合理性!
class Solution {
public:int integerBreak(int n) {if (n == 2) return 1;if (n == 3) return 2;if (n == 4) return 4;int result = 1;while (n > 4) {result *= 3;n -= 3;}result *= n;return result;}
};
96.不同的二叉搜索树 (可跳过)
思路:分析:
1.为1的时候只有一种,为2的时候只有两种,为3的时候5种
2.画出图,发现,为2的时候:左边为0右边有一个元素的情况和左边一个右边为0的情况。
为3的时候:左边为2右边为0,左边1右边1,左边0右边2的情况。由此就可以写出递推式了(值不重要,重要的是有几个,这几个的组合方式有几种)
五部曲:
1.dp[i]:从1到i个元素,共有几种不同的树
2.递推式:dp[i]+=dp[j-1]*dp[i-j]
3.初始化:dp[0]=1(空结点也为一颗二叉搜索树)
3.遍历:i从1开始,j从1开始。
注意:i需要从1开始,且可以到n;j从1开始,可以到i
代码:
class Solution {
public:int numTrees(int n) {vector<int>dp(n+1,0);dp[0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i]+=dp[i-j]*dp[j-1];}}return dp[n];}
};