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)``。