代码随想录算法训练营第四十五天|70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数

今天的题一道是求装满背包的可能情况;另两道都是求装满背包的所需的最小物品数目，不用考虑是组合还是排序问题

70. 爬楼梯 （进阶）

背包问题，求装满背包的个数问题

• 题目链接：代码随想录

• 解题思路：
  本题爬楼梯就是把之前需要递推的思路：dp[i] = dp[i - 1] + dp[i - 2]由前面两种状态推导而来，改为
  一共重量为i的背包(楼梯数)，用1和2重量装满，有几种方法，属于是背包问题求解例子

public int climbStairs(int n) {
    //1.确定dp数组，dp[i]表示装满第i容量的背包，有几种方法
    int[] dp = new int[n + 1];//初始化为n+1个背包
    //1.初始化
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {//先遍历背包
        for (int j = 1; j <= 2; j++) {//再遍历物品，因为物品的重量只有1和2
            /**
             * 改为一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
             * 这里物品遍历为1~m
             */
            if(i >= j){
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[n];
}

322. 零钱兑换

本题学到背包问题有很多变式，分析清楚递推条件，初始化和遍历顺序即能写出解

①求硬币的最小个数问题 -----> 求装满背包的选取的最小物品个数
②每种硬币的数量是无限的，可以看出是典型的完全背包问题

• 题目链接：代码随想录

• 解题思路：
  1. dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
  2.凑足总额为j - coins[i]的最少个数为dp[j - coins[i]].那么只需要加上一个钱币coins[i],即dp[j -coins[i]] + 1;
  所以公式为dp[j] = min(dp[j - coins[i]] + 1, dp[j])
  3.初始化：
  ①首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0
  ②再考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
  4.遍历顺序：本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列，所以for循环顺序不必纠结
  *

• 推导过程：

  

public int coinChange(int[] coins, int amount) {
    //1.定义dp数组，dp[i]表示凑足重量为i的背包所需要的最小物品数量
    int[] dp = new int[amount + 1];
    //2.初始化赋值
    int max = Integer.MAX_VALUE;
    for (int i = 1; i < dp.length; i++) {
        dp[i] = max;
    }
    dp[0] = 0;
    //3.遍历
    for (int i = 0; i < coins.length; i++) {//先遍历物品
        for (int j = coins[i]; j <= amount; j++) {//完全背包，正序遍历

            //确保dp[j - coins[i]]不是初始的最大值
            if (dp[j - coins[i]] != max) {
                //选择硬币数目最小的情况
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }

    }
    //判断amount重量是否更新，若未更新，那么说明没有结果
    return dp[amount] == max ? -1 : dp[amount];
}

279.完全平方数

• 题目链接：代码随想录

跟上一题对比来看

本题翻译：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

• 解题思路：
  本题同上题唯一不同之处是物品的形式
  上一题物品就是其本身，这一题物品是 i * i，不是放入原本的物品

• 推导过程：

  

public int numSquares(int n) {
    //1.定义dp数组,dp[i]表示装满容量为i的背包的最小选择物品数字
    //物品为1的平方，2的平方，3的平方...
    //本题唯一区别是物品不单单是数字本身，而是一个数的平方，凑成背包的物品是一个数的平方
    int[] dp = new int[n + 1];
    //2.初始化
    int max = Integer.MAX_VALUE;
    for (int i = 1; i <= n; i++) {
        dp[i] = max;
    }
    dp[0] = 0;//这里不能装入0 * 0的物品，因为题目从1开始
    //3.遍历
    for (int i = 1; i * i <= n; i++) {//先遍历物品，物品从1开始,还有这个终止条件
        for (int j = i * i; j <= n; j++) {
            //确定前一个背包状态有有效值
            if(dp[j - i * i] != max){
                dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
            }
        }

    }
    return dp[n];
}