leetcode322. 零钱兑换
给你一个整数数组 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] <= 231 - 1
0 <= amount <= 104
目录
题目描述
给定一组货币面额和一个总金额,计算可以凑出该总金额的硬币组合数。如果没有任何一种组合可以凑出该金额,则返回 -1。
算法分析
这个问题可以通过动态规划来解决。我们创建一个数组 dp
,其中 dp[j]
表示凑出金额 j
的最小硬币数量。我们遍历所有可能的硬币组合,并更新 dp
数组。
算法步骤
- 初始化一个数组
dp
,其大小为amount + 1
,所有元素初始化为无穷大,除了dp[0]
初始化为 0。 - 遍历所有可能的硬币组合。
- 对于每个硬币
coins[i]
,更新dp[j]
为min(dp[j], dp[j - coins[i]] + 1)
,其中j
是当前考虑的金额。 - 最后,检查
dp[amount]
是否为无穷大。如果是,则没有有效的组合;否则,返回dp[amount]
。
算法流程
具体代码
//dp[j] = min(dp[j], dp[j - coins[i]] + 1)
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX/2);
dp[0] = 0;
for (int i = 0; i < coins.size(); ++i) {
for (int j = 1; j <= amount; ++j) {
if (coins[i] <= j) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == INT_MAX/2 ? -1 : dp[amount];
}
};
算法分析
复杂度分析
- 时间复杂度:O(amount * coins.size()),其中
amount
是总金额,coins.size()
是硬币种类的数量。 - 空间复杂度:O(amount),我们需要一个数组来存储每个金额的最小硬币数量。
易错点
- 在初始化
dp
数组时,确保所有元素都被正确初始化。 - 在更新
dp
数组时,确保正确地计算最小硬币数量。 - 在检查是否有有效组合时,确保正确地处理无穷大的情况。
注意事项
- 确保在遍历硬币组合时不要超出数组的边界。
- 在处理数组时,确保不会覆盖任何元素。
相似题目
背包问题模板
背包分类:
1、0/1背包:外循环nums,内循环target,target倒序且target>=nums[i];
2、完全背包:外循环nums,内循环target,target正序且target>=nums[i];
问题分类:
1、最值问题:
dp[i] = max/min(dp[i], dp[i-nums]+1);
或
dp[i] = max/min(dp[i], dp[i-num]+nums);
2、存在问题(bool):
dp[i]=dp[i]||dp[i-num];
3、组合问题:
标签:背包,target,硬币,coins,amount,最值,数组,leetcode322,dp From: https://blog.csdn.net/qq_51350957/article/details/141326636dp[i]+=dp[i-num];