70. 爬楼梯

  1. if(n==1){
  2.     return 1;
  3. }else if(n==2){
  4.     return 2;
  5. }
  6. int[]dp=new int[n+1];
  7. dp[1]=1;
  8. dp[2]=2;
  9. for(int i=3;i<=n;i++){
  10.     dp[i]=dp[i-2]+dp[i-1];
  11. }
  12. return dp[n];

746. 使用最小花费爬楼梯

  1. if(cost.length==2){
  2.   return Math.min(cost[0],cost[1]);
  3. }
  4. int[]dp=new int[cost.length+1];
  5. for(int i=2;i<dp.length;i++){
  6.   dp[i]=Math.min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
  7. }
  8. return dp[dp.length-1];

62. 不同路径

  1. if(m==1||n==1){
  2.   return 1;
  3. }
  4. int[][]dp=new int[m][n];
  5. for(int i=1;i<m;i++){
  6.   dp[i][0]=1;
  7. }
  8. for(int i=1;i<n;i++){
  9.   dp[0][i]=1;
  10. }
  11. for(int i=1;i<m;i++){
  12.   for(int j=1;j<n;j++){
  13.     dp[i][j]=dp[i-1][j]+dp[i][j-1];
  14.   }
  15. }
  16. return dp[m-1][n-1];

63. 不同路径 II

  1. int row=obstacleGrid.length;
  2. int col=obstacleGrid[0].length;
  3. int[][]dp=new int[row][col];
  4. for(int i=0;i<row;i++){
  5.   if(obstacleGrid[i][0]==1){
  6.     break;
  7.   }else{
  8.     dp[i][0]=1;
  9.   }
  10. }
  11. for(int i=0;i<col;i++){
  12.   if(obstacleGrid[0][i]==1){
  13.     break;
  14.   }else{
  15.     dp[0][i]=1;
  16.   }
  17. }
  18. for(int i=1;i<row;i++){
  19.   for(int j=1;j<col;j++){
  20.     if(obstacleGrid[i][j]==1){
  21.       continue;
  22.     }else{
  23.       dp[i][j]=dp[i-1][j]+dp[i][j-1];
  24.     }
  25.   }
  26. }
  27. return dp[row-1][col-1];

343. 整数拆分

  1. if(n==2){
  2.   return 1;
  3. }
  4. int[]dp=new int[n+1];
  5. dp[1]=1;
  6. dp[2]=1;
  7. for(int i=3;i<=n;i++){
  8.   for(int j=1;j<=i/2;j++){
  9.     dp[i]=Math.max(Math.max(j*(i-j),j*dp[i-j]),dp[i]);
  10.   }
  11. }
  12. return dp[n];

96. 不同的二叉搜索树

  1. int[]dp=new int[n+1];
  2. dp[0]=1;
  3. dp[1]=1;
  4. for(int i=2;i<=n;i++){
  5.   for(int j=0;j<=i-1;j++){
  6.     dp[i]+=dp[j]*dp[i-j-1];
  7.   }
  8. }
  9. return dp[n];