LeetCode 518. 零钱兑换 II

约 4 分钟
文章信息 18 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 20-50 腾讯 字节 阿里 华为 微软 美团 拼多多 百度 快手 滴滴 虾皮 猿辅导
标签
数组 动态规划

题目描述

✅ 518. 零钱兑换 II

image-20260928200729788

image-20260928200729789

题意分析

给定若干种不同面额的硬币，每种硬币可以无限次使用，统计恰好凑出 amount 的组合数量。组合只看每种硬币使用了多少枚，不区分拿取顺序；凑不出来时返回 0。

这里求的是方案数，不是最少硬币枚数。目标金额为 0 时，不选任何硬币就是一份合法组合，因此答案为 1。候选面额都是正数，统计时需要同时允许同一硬币重复使用，并避免把不同排列重复计入。

解法：完全背包组合计数

核心思路

[!blue]

先按硬币种类分阶段。处理某种硬币之前，dp[j] 表示只使用已经处理过的硬币、凑出金额 j 的组合数。初始还没有任何硬币，只有金额 0 能用空组合凑出，所以 dp[0] = 1，其他位置为 0。

加入面额 coin 后，金额 j 的组合可以分成互不重叠的两类：不使用当前硬币，保留原来的 dp[j]；至少使用一枚当前硬币，去掉其中一枚后，剩下的就是允许使用当前硬币、凑出 j - coin 的组合。因此将这两类相加，得到 dp[j] += dp[j - coin]。

为让右侧状态已经允许使用当前硬币，金额必须从小到大更新。因为 coin 为正，j - coin < j，读到的较小金额已经是本轮状态，可以包含任意枚当前硬币；若倒序更新，读到的是上一阶段的状态，只能再加入一枚，便变成每种硬币最多使用一次。

外层固定硬币种类，则规定了组合形成时的处理顺序。一个组合只会在处理其中最后一种硬币时按使用数量被统计，不会因为硬币加入先后不同而重复。若反过来先枚举金额、再枚举最后加入的硬币，就会把不同最后一步视为不同方案，统计成排列。

每轮开始金额为 coin，更小的金额不可能使用当前面额，保留原值即可。遍历所有硬币后，dp[amount] 就覆盖了全部可用种类；全程只复用一维状态数组，不需要保存每个阶段的整张表。

解题步骤

  1. 创建长度为 amount + 1 的数组，设置 dp[0] = 1，其余为 0。
  2. 外层依次处理每种硬币 coin，不需要对面额排序。
  3. 内层从 j = coin 递增到 amount，执行 dp[j] += dp[j - coin]。
  4. 全部种类处理结束后，返回 dp[amount]。

代码实现

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];

        dp[0] = 1;

        // 先固定硬币种类，避免把不同选取顺序当成不同组合。
        for (int coin : coins) {
            // 金额正序让当前硬币可以继续重复使用。
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }

        return dp[amount];
    }
}

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1

    // 先固定硬币种类，避免把不同选取顺序当成不同组合。
    for _, coin := range coins {
        // 金额正序让当前硬币可以继续重复使用。
        for j := coin; j <= amount; j++ {
            dp[j] += dp[j-coin]
        }
    }
    return dp[amount]
}

复杂度分析

  • 时间复杂度：$O(c(A + 1))$，c 为硬币种类数，A 为目标金额。
  • 空间复杂度：$O(A + 1)$，保存金额零到 A 的状态，零金额也有一份空组合。

关键点总结

[!green]

  • 外层枚举硬币，保证统计的是组合而不是排列。
  • 金额正序更新，保证当前硬币可以重复使用。
  • dp[0] = 1 表示空方案，不能初始化为 0。
  • 完整二维状态是“前 k 种硬币凑出金额 j”，一维写法只是把 k 这一维滚动压缩。

易错点总结

[!yellow]

  • 交换内外循环：先枚举金额再枚举最后一枚硬币，会把不同拿取顺序计成不同方案。
  • 金额倒序更新：右侧读到上一阶段的状态，会限制当前硬币只能使用一次。
  • 遗漏 dp[0] = 1：没有空组合这个起点，其他金额无法产生任何方案。
  • 把 += 写成赋值：会覆盖不使用当前硬币的已有方案，应将两类互不重复的组合相加。
  • 用最小值转移：本题累计组合数，应做加法；最小值转移解决的是最少硬币枚数。

相似题目

题目 难度 关联与区别
322. 零钱兑换 中等 候选硬币都可重复使用，原题求最少枚数，本题统计不区分顺序的组合数。
377. 组合总和 Ⅳ 中等 两题都计数，但原题不同排列顺序算不同方案，循环顺序不能混用。
279. 完全平方数 中等 按金额或目标长度累积可重复选择的结果；本题先枚举硬币以统计无序组合，该题候选值为完全平方数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/99921078
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！