代码随想录训练营day34|62.不同路径，63. 不同路径 II,343.整数拆分,96.不同的二叉搜索树

本文主要是介绍代码随想录训练营day34|62.不同路径，63. 不同路径 II,343.整数拆分,96.不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不同路径1

题目
题目并不难想，每一个点只有两种走到的方法，要么从左侧来，要么从上侧来，所以 dp[i][j]=dp[i-1][j]+dp[i][j-1];

 		vector<vector<int>> dp(m,vector<int>(n,0)); for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(i>0&&j>0){dp[i][j]=dp[i-1][j]+dp[i][j-1];  }elsedp[i][j]=1;                }}return dp[m-1][n-1];

不同路径2

题目
唯一的区别在于有了障碍，我的方式是面对有障碍的地方dp直接设为0，
然后这题初始化时要注意，碰到障碍后剩下的一行或一列都是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));for(int j=0;j<n;j++){if(obstacleGrid[0][j]==1){break;}dp[0][j]=1;}for(int i=0;i<m;i++){if(obstacleGrid[i][0]==1){break;}dp[i][0]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==1)dp[i][j]=0;else{dp[i][j]=dp[i-1][j]+dp[i][j-1];}}}return dp[m-1][n-1];}
};

343.整数拆分

思路：如果是一个数分为两个数然后求乘积的话，那肯定是对半分最大（a+b=c，ab月考及乘积越大），所以对拆完的两个数再分别对半拆

好吧这个思路并不正确，因为8拆成2 3 3比4 和4 的乘积更大。
可以考虑用dp数组来记录第i个位置的拆分最大乘积
而这题的难处就在于它的递推规律并没有那么直接，
对一个数n，可以先将它分解为两个数，一个数从1一直到n/2，因为再多就是重复了。
然后另一边的数可以拆分成它的最大乘积形式（5拆成23会比5大），也可能不拆会更大（3比拆成12要大），所以取max
在这里插入图片描述

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[0]=0;dp[1]=0;dp[2]=1;for(int i=3;i<=n;i++){for(int j=1;j<=i/2;j++){dp[i]=max(dp[i],j*max((i-j),dp[i-j]));}}return dp[n];}
};

96.不同的二叉搜索树

n个数的话
取中间的数为i，则左边有i-1个数，右边有n-i个数
左边有dp[i-1]种情况，右边有dp[n-i]种情况，所以dp[n]+=dp[i-1]*dp[n-i]；

class Solution {
public:int numTrees(int n) {vector<int>dp(n+1);if(n==1)return 1;else if(n==2)return 2;dp[0]=1;dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){for(int k=i;k>=1;k--){dp[i]+=dp[k-1]*dp[i-k];}}return dp[n];}
};