动态规划

Leetcode 198:
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路 ： dp[0] = nums[0] ; dp[1] = max(nums[0],nums[1]); dp[i] = max(dp[i-1],dp[i-2]+nums[i])
代码

class Solution {
    public int rob(int[] nums) {
      if(nums.length==0) return 0;
      if(nums.length==1) return nums[0];
      if(nums.length==2) return Math.max(nums[0],nums[1]);
      int dp []  = new int [3];
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0],nums[1]);
      for(int i = 2;i<nums.length;i++){
          dp[2] = Math.max(dp[0]+nums[i],dp[1]);
          dp[0]  =dp[1];
          dp[1] = dp[2];
      }
      return dp[2];
    }
}

Leetcode 93 :最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路： dp[0] =nums[0] , dp[i]={dp[i−1]+nums[i],ifdp[i−1]≥0nums[i],ifdp[i−1]<0 ,maxSum =nums[0]; maxSum=max(dp[i],maxSum)

class Solution {
    public int maxSubArray(int[] nums) {
     if(nums==null || nums.length==0) return 0;
     if(nums.length ==1) return nums[0];
      int maxSum =nums[0];
      int dp1 = nums[0];
       int dp2 =0;
       for(int i=1;i<nums.length;i++){
           dp2 = dp1>0 ? dp1+nums[i] : nums[i];
           dp1 =dp2;
           maxSum = Math.max(maxSum,dp2);
       }
       return maxSum;
    }
}

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1
dp[] 初始值赋值为 -1 ；dp[0] =0 ;dp[n] =-1 n<0; dp[n] =min(dp[n],dp[n-conins[j]]+1);

class Solution {
    public int coinChange(int[] coins, int amount) {
//      int dp [] = new int [amount+1];
//      Arrays.fill(dp,-1);
//      dp[0] =0;
//    for(int i=1 ;i<amount+1;i++){
//        for(int j= 0;j<coins.length;j++){
//            if(i-coins[j]>=0 && dp[i-coins[j]]!=-1){
//                if(dp[i]==-1 || dp[i]>dp[i-coins[j]]+1){
//                    dp[i] =dp[i-coins[j]]+1;
//                }
//            }
//        }
//    }
//    return dp[amount];

      int dp []= new int [amount+1];
      Arrays.fill(dp,-1);
      dp[0]=0;
      for(int i=0;i<amount+1;i++){
          for(int j =0;j<coins.length;j++){
              if(i<coins[j]) continue;
              else{
                if(dp[i]==-1&&dp[i-coins[j]]!=-1) dp[i] = dp[i-coins[j]]+1;
                else if(dp[i]!=-1&&dp[i-coins[j]]!=-1){
                 dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                }
          }
      }

    }
    return dp[amount];
}
}

Leetcode 518 零钱兑换2
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

class Solution {
    public int change(int amount, int[] coins) {
     int dp [] = new int [amount+1];

     dp[0]=1;
     for(int coin:coins){
         for(int i=0;i<dp.length;i++){
             if(i>=coin)
             dp[i] = dp[i]+dp[i-coin];
         }
     }
     return dp[amount];
    }
}

class Solution {
    public int change(int amount, int[] coins) {
     int dp [] = new int [amount+1];

     dp[0]=1;
     for(int coin:coins){
         for(int i=coin;i<dp.length;i++){

             dp[i] = dp[i]+dp[i-coin];
         }
     }
     return dp[amount];
    }
}

Leetcode 120:三角形最下路径和：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

//o（N^2）
// class Solution {
//     public int minimumTotal(List<List<Integer>> triangle) {
//      int len = triangle.size();
//      int dp[][] = new int [len][len];
//      if(triangle==null) return 0;
//      if(len==1) return triangle.get(0).get(0);
//      dp[0][0] = triangle.get(0).get(0);
//      int min = Integer.MAX_VALUE;
//      for(int i= 1;i<len;i++){
//           for(int j=0;j<i;j++){
//              if(j==0) dp[i][0] = dp[i-1][0]+triangle.get(i).get(0);
//              else{
//               dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i).get(j);
//              }
//               if(i == len-1)  min = Math.min(min,dp[i][j]);
//              }
//              dp[i][i] = dp[i-1][i-1] +triangle.get(i).get(i);


//      }
//       min = Math.min(min,dp[len-1][len-1]);
//      return min;

//     }
// }
//空间优化  这个方法从下到上避免了最后求解最后一行最小值带来重复计算 ，逆向思维
class Solution{
    public int minimumTotal(List<List<Integer>> triangle){
        int len = triangle.size();
        int dp[] =new int [len+1];
        for(int i=len-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                dp[j]= Math.min(dp[j],dp[j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}
//递归遍历
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return  dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) {
            return 0;
        }
        return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }
}
//递归暴力 进行记忆优化
class Solution {
    Integer[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return  dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }
}