0518. Coin Change II

题目信息

题号:

0518

难度:

Medium

主题:

硬币组合、无限使用、目标金额、顺序去重

原题:

LeetCode 0518

重点:

每种面额可使用任意次、不同排列属于同一种组合、无法组成时返回 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)。