0518. Coin Change II¶
题目信息¶
- 题号:
0518
- 难度:
Medium
- 主题:
硬币组合、无限使用、目标金额、顺序去重
- 原题:
- 重点:
每种面额可使用任意次、不同排列属于同一种组合、无法组成时返回 0、金额为 0 时有一种空组合
题目重述¶
给定非负整数 amount 和一组互不相同的正整数硬币面额 coins。每种面额可以使用任意多次,统计有多少种不同的硬币组合能够使总金额恰好等于 amount。
组合只按各面额的使用次数区分,硬币排列顺序不同不产生新答案。若无法组成目标金额,返回 0;当 amount = 0 时,不选择任何硬币是一种有效组合,因此返回 1。
自建示例¶
同一组合不按顺序重复计数:
输入:amount = 6,coins = [1,3,4]
输出:4
解释:四种组合分别是 1+1+1+1+1+1、3+1+1+1、3+3、4+1+1。改变硬币排列顺序不形成新组合。
金额为零:
输入:amount = 0,coins = [2,5]
输出:1
解释:唯一方案是不使用任何硬币。
硬币外层保证组合不重复¶
令 dp[x] 表示只使用已经处理的面额组成金额 x 的组合数。对每种硬币先遍历,再从该面额向金额上升更新,等价于决定该面额使用 0 次、1 次或更多次;由于面额的处理顺序固定,1+1+4 和 4+1+1 不会被当成两种组合。
dp[0] = 1 表示空组合,后续所有组合都由它扩展而来。
C++ 实现¶
class Solution {
public:
int change(int amount, std::vector<int>& coins) {
std::vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins) {
for (int value = coin; value <= amount; ++value) {
dp[value] += dp[value - coin];
}
}
return dp[amount];
}
};
代码分析¶
外层面额顺序把每种组合归到唯一的“最后处理面额”路径,内层正序又允许同一面额重复使用。每种面额和每个金额各处理一次,时间复杂度为 O(amount * coins.size()),空间复杂度为 O(amount)。