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