动态规划、背包问题 6/22 96-100

1.爬楼梯（ LeetCode 70 ）动态规划

方法一：递归 (超时)

class Solution {
    
        int ans;
        public int climbStairs(int n) {
    
             dfs(0,n);
             return ans;
        }
        public void dfs(int i,int n){
    
            if (i > n)return;
            if (i == n)ans++;
            dfs(i + 1,n);
            dfs(i + 2,n);
        }

    }

方法二：动态规划
多想几个用例，看看是否存在规律

class Solution {
    
        public int climbStairs(int n) {
    
            if (n < 3) return n;
            //dp[i] 爬到第i级楼梯的方案数
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
    
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }

方法三：
使用滚动数组思想对方法二优化

 class Solution {
    
        public int climbStairs(int n) {
    
            if (n < 3) return n;
            int p = 1;
            int q = 2;
            int r = 0;
            for (int i = 3; i <= n; i++) {
    
                r = p + q;
                p = q;
                q = r;
            }
            return r;
        }
    }

2.最大子数组和（ LeetCode 53 ）

动态规划

class Solution {
    
        public int maxSubArray(int[] nums) {
    
            //dp[i] 已第i个数结尾的最大子数组和
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int ans = dp[0];
            for (int i = 1; i < nums.length; i++) {
    
                dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
                if (dp[i] > ans)ans = dp[i];
            }
            return ans;
        }
    }

3.零钱兑换（ LeetCode 322 ）

方法一：记忆化数组
分治思想，把大问题分解为小问题
记忆化数组，存储已经计算过的数值，当再次遇到相同数值时不用重复计算

public class Solution {
    
  public int coinChange(int[] coins, int amount) {
    
    // 初始条件检查
    if (amount < 1) return 0;
    // 动态规划入口
    return coinChange(coins, amount, new int[amount]);
  }

  /** * 自上而下的动态规划方法 * coins:硬币面额 * rem:余额 * count:存储中间计算结果，空间换时间，count为记忆化数组,空间换时间 */
  private int coinChange(int[] coins, int rem, int[] count) {
    
    // 结束条件：此路径不通
    if (rem < 0) return -1;
    // 结束条件：余额为0，成功结束
    if (rem == 0) return 0;
    // 之前已经计算过这种情况，直接返回结果，避免重复计算
    if (count[rem - 1] != 0) return count[rem - 1];
    int min = Integer.MAX_VALUE;
    // 遍历当前递归子树的每一种情况
    for (int coin : coins) {
    
      // 用一下coin这个面值的硬币会怎样？res是这个方法的最优情况
      int res = coinChange(coins, rem - coin, count);
      // res<0 即为 res=-1,此法失败，res>min不是最优情况，舍去
      if (res >= 0 && res < min)
        min = 1 + res;
    }
    // count[rem - 1]存储着给定金额amount的解
    // 若为Integer.MAX_VALUE则该情况无解
    count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
    return count[rem - 1];
  }
}

方法二:动态规划 完全背包 朴素数组

class Solution {
    
        public int coinChange(int[] coins, int amount) {
    
            if (amount == 0)return 0;
            int[][] dp = new int[coins.length][amount + 1];
            for (int i = 0; i <= amount; i++) {
    
                int k = i / coins[0];
                if (k * coins[0] == i)dp[0][i] = k;
                else dp[0][i] = -1;
            }

            for (int i = 1; i < coins.length; i++) {
    
                int coin = coins[i];
                for (int j = 0; j <= amount; j++) {
    
                    //不选本枚硬币
                    int x = dp[i - 1][j];
                    //选本枚硬币
                    int y = Integer.MAX_VALUE;//y = Integer.MAX_VALUE时代表不能选择本枚硬币
                    for (int k = 1; ; k++) {
    
                        if (k * coin > j)break;
                        int z = dp[i - 1][j - k * coin];
                        y = Math.min(y,z == -1 ? Integer.MAX_VALUE : z + k);
                    }
                    if (x == -1){
    
                        dp[i][j] = y == Integer.MAX_VALUE ? -1 : y;
                    }else {
    
                        dp[i][j] = Math.min(x,y);
                    }
                }
            }
            return dp[coins.length - 1][amount];
        }
    }

方法三：完全背包 一维数组

 class Solution {
    
        public int coinChange(int[] coins, int amount) {
    
            if (amount == 0)return 0;
            int[] dp = new int[amount + 1];
            for (int i = 0; i <= amount; i++) {
    
                int k = i / coins[0];
                if (k * coins[0] == i)dp[i] = k;
                else dp[i] = -1;
            }

            for (int i = 1; i < coins.length; i++) {
    
                int coin = coins[i];
                for (int j = 0; j <= amount; j++) {
    
                    //不选本枚硬币
                    int x = dp[j];
                    //选本枚硬币
                    int y = Integer.MAX_VALUE;//y = Integer.MAX_VALUE时代表不能选择本枚硬币
                    if (j - coin >= 0 && dp[j - coin] != -1){
    
                        y = dp[j - coin] + 1;
                    }
                    if (x == -1){
    
                        dp[j] = y == Integer.MAX_VALUE ? -1 : y;
                    }else {
    
                        dp[j] = Math.min(x,y);
                    }
                }
            }
            return dp[amount];
        }
    }

4.零钱兑换 II（ LeetCode 518 ）

官方解：动态规划

//动态规划
    class Solution {
    
        public int change(int amount, int[] coins) {
    
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            //外层遍历coins，保证了硬币放入的顺序
            //比如coins = 1，2 amount = 1时
            //先出现的一定是 1 1，然后才是2 2
            for (int coin : coins) {
    
                for (int i = coin; i <= amount; i++) {
    
                    dp[i] += dp[i - coin];
                }
            }
            return dp[amount];
        }
    }

解法二：完全背包 朴素数组

  class Solution {
    
        public int change(int amount, int[] coins) {
    
            //dp[i][j] 前i个数中选择凑成金额j的方案数
            int[][] dp = new int[coins.length][amount + 1];
            for (int i = 0; i <= amount; i++) {
    
                //i % coins[0] == 0代表第一枚硬币可以凑出金额i
                dp[0][i] = (i % coins[0] == 0) ? 1 : 0;
            }
            for (int i = 1; i < coins.length; i++) {
    
                int coin = coins[i];
                for (int j = 0; j <= amount; j++) {
    
                    dp[i][j] = dp[i - 1][j];//不选coin的方案数
                    for (int k = 1;; k++) {
    //选coin的方案数
                        if (k * coin > j)break;
                        dp[i][j] += dp[i - 1][j - k * coin];//加上选k枚硬币的方案数
                    }
                }
            }
            return dp[coins.length - 1][amount];
        }
    }

方法三：完全背包 一维数组

 class Solution {
    
        public int change(int amount, int[] coins) {
    
            //dp[i][j] 前i个数中选择凑成金额j的方案数
            int[] dp = new int[amount + 1];
            //初始化
            for (int i = 0; i <= amount; i++) {
    
                dp[i] = i % coins[0] == 0 ? 1 : 0;
            }
            for (int i = 1; i < coins.length; i++) {
    
                int coin = coins[i];
                for (int j = 0; j <= amount; j++) {
    
                    if (j - coin >= 0){
    
                        dp[j] += dp[j - coin]; 
                    }
                }
            }
            return dp[amount];
        }
    }

5.最小路径和（ LeetCode 64 ）

动态规划

class Solution {
    
        public int minPathSum(int[][] grid) {
    
            int[][][] dp = new int[grid.length][grid[0].length][2];
            for (int i = 0; i < grid.length; i++) {
    
                for (int j = 0; j < grid[0].length; j++) {
    
                    dp[i][j][0] = Integer.MAX_VALUE;
                    dp[i][j][1] = Integer.MAX_VALUE;
                }
            }
            //dp[i][j][0] 上一个元素在左边
            //dp[i][j][1] 上一个元素在上边
            dp[0][0][0] = grid[0][0];
            //初始化dp第一行
            for (int i = 1; i < grid[0].length; i++) {
    
                dp[0][i][0] = grid[0][i] + dp[0][i - 1][0];
            }
            //初始化dp第一列
            dp[0][0][1] = grid[0][0];
            for (int i = 1; i < grid.length; i++) {
    
                dp[i][0][1] = grid[i][0] + dp[i - 1][0][1];
            }
            for (int i = 1; i < grid.length; i++) {
    
                for (int j = 1; j < grid[0].length; j++) {
    
                    //上一个元素在左边
                    dp[i][j][0] = Math.min(dp[i][j - 1][0],dp[i][j - 1][1]) + grid[i][j];
                    //上一个元素在上面
                    dp[i][j][1] = Math.min(dp[i - 1][j][0],dp[i - 1][j][1]) + grid[i][j];
                }
            }

            return Math.min(dp[grid.length - 1][grid[0].length - 1][0]
                    ,dp[grid.length - 1][grid[0].length - 1][1]);
        }
    }