代码随想录算法训练营打卡Day45 | LeetCode70 爬楼梯、LeetCode322 零钱兑换、LeetCode279 完全平方数

摘要

• 用背包问题的思路解决具体问题时，要明确什么是物品，物品的重量是什么，物品的价值是什么，以及要求的背包的状态是什么（装入的价值最大、装满背包使用的物品数最少，装满背包有多少种方法等等）
• 先遍历背包，再遍历物品，求的是排列数。先遍历物品，再遍历背包，求的是组合数。如果不关心具体如何放入物品，一般不需要考虑遍历顺序。

LeetCode70 爬楼梯

70. 爬楼梯 - 力扣（Leetcode）

• 这道题目用类似斐波那契数列的思路，直接进行动态规划的分析：
  • dp数组及下标的含义：爬到第j级台阶，有dp[j]种方法。
  • dp[j]有两种可能推出：从第j-1级台阶向上爬一级，从第j-2级台阶向上爬两级。

题解代码如下

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        if (dp.size() > 1) dp[1] = 1;
        for (int i = 2; i < dp.size(); i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

• 这道题目也可以用完全背包的思路来解决

• 每一步爬1阶，2阶，.... m阶就是物品，楼顶就是背包。

• 每一步爬的阶数可以重复使用，例如跳了1阶，还可以继续跳1阶。

• 问跳到楼顶有几种方法其实就是问装满背包有几种方法。

爬楼梯（完全背包）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 到 m 个台阶。你有多少种不同的方法可以爬到楼顶呢？

• dp数组及下标的含义：爬到第j级台阶，有dp[j]种方法。对于第0级台阶到第n级台阶，每遍历到一级台阶，dp[j]更新一次。
• 确定递推公式
  1. 在第0级台阶或者说在起点，起点是唯一的，在起点只有一种方法，dp[0]=1。其他台阶目前还没有走到，所以其他dp[j]都初始化成0。
  2. 对于dp[j]，最多有m种更新的可能：即从第j-k级台阶爬k级，到达第j级台阶。。
• dp数组的初始化，由递推公式的推导得到。
• 确定遍历顺序：在代码随想录算法训练营打卡Day44中，分析了完全背包问题中，装满背包的排列数和组合数的问题。本题中，先爬1级再爬2级和先爬2级再爬1级是不同的方法，和物品选择的先后顺序有关。本题要求的是排列数，所以先遍历背包，再遍历物品。

根据完全背包问题的思路写出的题解代码如下，在 LeetCode70 中，m设为2

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        
        int m = 2;
        for (int j = 0; j <= n; j++) {
            for (int i = 1; i <= m; i++) {
                dp[j] += j >= i ? dp[j - i] : 0;
            }
        }

        return dp[n];
    }
};

LeetCode322 零钱兑换

322. 零钱兑换 - 力扣（Leetcode）

• 这道题目和完全背包问题有一点不同，完全背包问题要求的是背包能装入的物品的最大价值，本题要求的是刚好装满背包最少的物品数。
• 要用完全背包问题的思路来解决题目，就首先要明确什么是物品，什么是背包，还要明确物品的价值是什么，重量是什么。
  • 零钱是物品，零钱的面额是重量，还是零钱的个数是重量呢？这要看我们如何定义装满背包，因为题目要求装入的零钱要凑成总金额amount，所以将装满背包定义为装入的零钱的总金额为amount是比较合适的。这也就是说，零钱的面额是”重量“
• dp数组及数组下标的含义：
  • dp[i][j]表示的是从从第0种到第i种零钱中任选，凑成总金额为j所需的最少零钱个数。
  • dp[j]表示的是，凑成总金额为j所需的最少零钱个数。
• 确定递推公式，
  • 首先，之前没有放过零钱，只选一种面额的零钱i，面额为coins[i]，能凑成的总金额是coins[i]的倍数，dp[k*coins[i]]=1。
  • 假设之前从第0种到第i-1种零钱中任选放入了背包，且放入的零钱数最少，现在尝试再放入第i种零钱，有两种可能：
    1. 不放零钱无论coins[i]替换之前放入背包的哪种零钱，都不会使放入的零钱数最少，所以不放入第i种零钱，尝试完coins[i]的dp[j]不变。
    2. 放入coins[i]替换之前放入背包的零钱，会使得放入的零钱数变少，由于可能之前已经放入过coins[i]，
       • 所以二维dp数组的表示方法是 其中符合dp数组的定义，因为之前可能放入过第i种零钱。如果取，就不符合dp数组的定义了。
       • 对于一维dp数组，关键在于遍历顺序。放入coins[i]是一个一个逐个放入的，而越大的背包能放入的个数越多，应该从小到大遍历背包，对应一个一个coins[i]尝试放入背包的过程。
• 初始化dp数组，如果总金额为0，一个硬币都不需要放入，所以dp[0]=0。而其他dp[j]，由于之后的递推公式要取最小值，所以应设定为一个不影响取最小值的值，
  • 要注意，出现了加法，如果初始值为INT_MAX，会发生整形溢出，所以初始化的值应为INT_MAX - 1
  • 其实题目也有提示，硬币的数量不超过

• 遍历顺序，完全背包问题，遍历背包容量时，应从小到大遍历背包容量。

题解代码如下

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX - 1);

        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        return dp[amount] != INT_MAX - 1 ? dp[amount] : -1;
    }
};

LeetCode279 完全平方数

• 本题和上一题思路基本一致，只是需要对”物品“多做一些处理，完全平方数是”物品“，数值为”重量“，要求的是装满背包所需的最少物品数，即和为n的完全平方数的最少数量。
  • 可选的完全平方数的数值不会大于n，所以虽然题目没有给出哪些”物品“可选，但可以通过n的值推出。
• dp[j]表示的是，从小于或等于n的完全平方数中任选k个数，值相同的完全平方数可以多次选取，选取出的完全平方数的和等于j，且最小的k即为dp[j]的值。即dp[j]为和为j的完全平方数的最少个数。

题解代码如下

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX - 1);
        dp[0] = 0;
        
        for (int i = 1; pow(i, 2) <= n; i++) {
            int temp = pow(i, 2);
            for (int j = temp; j <= n; j++) {
                dp[j] = min(dp[j], dp[j - temp] + 1);
            }
        }

        return dp[n];
    }
};