代码随想录day34 动态规划2
题目：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));
//如果障碍在开始或者终点，直接return
if(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];
}
};