本文主要是介绍【做一道算一道】零钱兑换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
零钱兑换
给你一个整数数组 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]
这篇关于【做一道算一道】零钱兑换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
