题目：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];}
};
