【做一道算一道】零钱兑换

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^(31) - 1
0 <= amount <= 10^4

思路

虽然是在刷dp的题，但是一眼就想到回溯，写了个回溯的，果不其然超时。
再从完全背包的角度来看，感觉怪怪的，没太想明白。
看了题解大概懂了：代码随想录：零钱兑换
这个完全背包正好初始化和dp[0]的设置和前面的相反，

代码

超时的回溯

class Solution {
private:
int cnt=0;
int min_cnt=INT_MAX;
    void backtracking(vector<int>& coins, int& amount){
        if(amount==0){
            min_cnt=min(cnt,min_cnt);
        }else if(amount<0){
            return;
        }
        for(int i=coins.size()-1;i>=0;i--){
            amount-=coins[i];
            cnt++;
            backtracking(coins,amount);
            amount+=coins[i];
            cnt--;
        }
    }

public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0) return 0;
        if(amount<coins[0]) return-1;
        backtracking(coins,amount);
        if(min_cnt!=INT_MAX)
        return min_cnt;
        else 
        return -1;
    }
};

完全背包

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

因为初始化的dp为INT_MAX，所以加一道判断，避免溢出

 if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
举例推导dp数组
以输入：coins = [1, 2, 5], amount = 5为例

初始时，dp数组被初始化为INT_MAX，除了dp[0]被设置为0，因为0金额不需要任何硬币。
数组如下：
dp = [0, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX]
逐步填充dp数组：

当coins[0] = 1时：
从j = 1开始，因为1是最小的硬币面额。
更新dp[1]为1（因为1个1元硬币就可以组成1）。
继续增加j，更新dp[j]为dp[j - 1] + 1（因为可以再加一个1元硬币）。
结果：dp = [0, 1, 2, 3, 4, 5]

当coins[1] = 2时：
从j = 2开始，因为2是当前硬币的面额。
更新dp[2]为1（因为1个2元硬币就可以组成2），这比之前的dp[2]（2）更优。
由于dp[2]已更新，现在可以更新dp[4]为dp[4 - 2] + 1 = 1 + 1 = 2（因为2个2元硬币可以组成4）。
继续增加j，对于j = 3和j = 5，由于没有直接的硬币面额，我们不能直接更新dp[j]，但可以比较dp[j - 2] + 1和当前的dp[j]，发现对于j = 3和j = 5，当前的dp[j]已经是更优的解。
结果：dp = [0, 1, 1, 2, 2, 3]

当coins[2] = 5时：
从j = 5开始，因为5是当前硬币的面额。
更新dp[5]为1（因为1个5元硬币就可以组成5），这是最优解。
结果：dp = [0, 1, 1, 2, 2, 1]

最终，dp数组变为：
dp = [0, 1, 1, 2, 2, 1]