LeetCode 518. 零钱兑换 II

约 5 分钟
文章信息 18 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 虾皮
标签
数组 动态规划 背包问题 完全背包问题 完全背包 零钱兑换问题
目录

题目描述

✅ 518. 零钱兑换 II

image-20250507222013360

image-20250507221913737

题意分析

给定一个面额数组 coins 和一个目标金额 amount，问有多少种方式可以正好凑出这个金额，返回方案的数量。

题面里有三个必须先咬准的信号。第一，每种硬币的数量是无限的，也就是同一个面额可以被反复使用，这与「每个物品只能拿一次」的场景有本质区别。第二，题目只问有多少种，不要求把方案本身列出来，因此不需要保存任何路径信息，只需要一个能相加的计数。第三，也是最关键的一点，顺序不同算同一种：先拿 1 再拿 2 和先拿 2 再拿 1 都是「一个 1 加一个 2」，只能计一次。换句话说，一个方案的身份由「每种面额各用了几枚」这个多重集合唯一决定，而不是由取用的先后次序决定。

边界方面有两处要留意。其一，amount 可以为 0，此时正确答案是 1——什么都不拿本身就是一种合法的凑法，这个约定后面会直接决定初始值怎么设。其二，coins 里的面额互不相同且都为正数，所以不会出现面额为 0 导致自我循环的情况，但完全可能所有面额都大于 amount，此时答案是 0。

题目还保证结果在 32 位有符号整数范围内，这说明不需要为溢出做额外处理，可以放心用 int 累加。

解法：完全背包组合计数

核心思路

问题关键：每种硬币可重复使用，但顺序不同不算新方案。例如 1 + 2 与 2 + 1 是同一种组合，因此既要满足“完全背包”，又要避免排列重复。

为什么选一维动态规划：定义 dp[j] 为“只使用当前已经枚举过的硬币，凑出金额 j 的组合数”。处理面额 coin 时：

\[dp[j] = dp[j] + dp[j-coin]\]

前一项是不使用 coin 的方案，后一项是在凑出 j-coin 的每个方案后再放一枚 coin。金额从小到大枚举，使本轮刚更新的状态还能继续参与转移，因此同一面额可以使用多次。

不变量与正确性：处理完前 k 种硬币后，dp[j] 恰好记录只用这 k 种硬币凑出 j 的组合数。任一方案按“是否使用第 k 种硬币”可唯一分成两类，转移不重不漏。外层按硬币枚举，还给每个组合规定了固定的加入顺序，所以 [1,2] 不会再以 [2,1] 被统计。

初始化 dp[0] = 1，表示凑出金额 0 有一种空方案，也是所有有效计数的起点。若外层改为枚举金额，统计结果会变成排列数；若金额倒序，当前硬币只能使用一次。

解题步骤

  • 创建长度为 amount + 1 的数组，令 dp[0] = 1。
  • 外层逐个枚举硬币 coin，固定组合中硬币的加入顺序。
  • 内层从 coin 正序枚举到 amount，执行 dp[j] += dp[j-coin]。
  • 返回 dp[amount]。

以 amount = 5, coins = [1,2,5] 为例，处理三种硬币后，dp 依次变为 [1,1,1,1,1,1]、[1,1,2,2,3,3]、[1,1,2,2,3,4]，答案为 4。

代码实现

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(n \cdot amount)$，其中 n 是硬币种类数。
  • 空间复杂度：$O(amount)$，使用一维数组保存状态。

关键点总结

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

易错点总结

  • 交换循环顺序：amount = 5, coins = [1,2,5] 会得到 9，把不同顺序当成不同方案。
  • 金额倒序更新：会退化为 0-1 背包，每种硬币最多使用一次。
  • 遗漏 dp[0] = 1：所有状态都无法从 0 累加起来，最终答案恒为 0。
  • 把 += 写成赋值：会覆盖“不使用当前硬币”的已有方案。
  • 混淆 322 题：本题求方案数用累加；零钱兑换求最少枚数用取最小值。

相似题目

题目 难度 考察点
377. 组合总和 Ⅳ 中等 同一份转移求排列数，循环顺序与本题正好相反
322. 零钱兑换 中等 同样的完全背包骨架，但求最少枚数而非方案数
279. 完全平方数 中等 物品由平方数隐式生成，考察把题面翻译成背包
416. 分割等和子集 中等 0-1 背包可行性，内层必须倒序，是正序的直接对照
494. 目标和 中等 先做数学变形转成子集和计数，再套 0-1 背包方案数
474. 一和零 中等 二维容量的 0-1 背包，考察多约束下的倒序压缩
1449. 数位成本和为目标值的最大数字 困难 完全背包求恰好装满下的字典序最大解，需要回溯构造串
LCR 103. 零钱兑换 中等 322 题的同题异号，适合用来复查最值型初始化
LCR 104. 组合总和 Ⅳ 中等 377 题的同题异号，可与本题对照检验循环顺序
面试题 08.11. 硬币 中等 固定面额的组合计数，额外要求对大数取模