5. LeetCode63. 不同路径 II

1.动态规划二维表 class Solution { public:     int uniquePathsWithObstacles(vector>& obstacleGrid) {         //dp[i][j]：到达[i][j]的方法数         int m=obstacleGrid.size();         int n=obstacleGrid[0].size();         vector>dp(m,vector(n));         //初始化dp，如果第0行和第0列有障碍物，那么其右边或下边的格子无法抵达         for(int i=0;i>& obstacleGrid) {         int m=obstacleGrid.size();         int n=obstacleGrid[0].size();          if(m==1){             for(int j=0;jdp(n);//滚动数组         //初始化dp         for(int j=0;j0)dp[j]=dp[j-1]+dp[j];             }         }         return dp[n-1];     } };

6. LeetCode343. 整数拆分

1.动态规划 class Solution { public:     int integerBreak(int n) {         //特殊情况         if(n<2){             return 0;         }          //dp[i]：拆分数字i的最大乘积         vectordp(n+1);         //初始化dp         dp[2]=1;         for(int i=3;i<=n;i++){             for(int j=1;j<=i/2;j++){//3拆分成1和2，所以从1开始                 //把i拆分成i-j和j两个数                 //或者拆分成j和其他数(数量>1)，只需要直到被拆分数的最大乘积即可                 dp[i]=max(dp[i],max((i-j)*j,j*dp[i-j]));             }         }         return dp[n];     } }; 时间复杂度：O(n^2) 空间复杂度：O(n)  2.数论 class Solution { public:     int integerBreak(int n) {         //特殊情况         if(n==2)return 1;         if(n==3)return 2;         if(n==4)return 4;//4=(2+2)=>2*2>3*1          int res=1;         while(n>4){             res*=3;             n-=3;         }         res*=n;         return res;     } }; 时间复杂度：O(n) 空间复杂度：O(1)

7. LeetCode96. 不同的二叉搜索树

本题我们只用管有i个节点时的结构数，不用管值。因为值都是不同的，所以可以把结构安排好后再把值填入即可。      class Solution { public:     int numTrees(int n) {         //dp[i]：节点个数为i的二叉搜索树结构数         vectordp(n+1);                  //初始化dp         dp[0]=1;         dp[1]=1;                  for(int i=2;i<=n;i++){//整棵树节点个数             for(int j=0;j<=i-1;j++){//左子树节点个数                 dp[i]+=dp[j]*dp[i-j-1];             }         }         return dp[n];     } };