LeetCode 面试题 08.11. 硬币

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 字节 阿里
标签
数组 动态规划 数学

题目描述

✅ 面试题 08.11. 硬币

image-20260928230526240

题意分析

有面额为一、五、十、二十五的硬币，每种可以使用任意多枚，统计凑出金额 n 的不同组合数，并对 10^9 + 7 取模。

组合只由各面额使用多少枚决定，取出这些硬币的顺序不构成新方案。既不是求最少硬币数，也不是统计按先后顺序排列的取币过程；同一面额可以反复选择。

解法：一维完全背包计数组合

核心思路

[!blue]

按固定顺序逐种加入允许使用的面额。处理到当前硬币 coin 时，dp[i] 表示只使用已经处理过的面额，凑出金额 i 的组合数。初始没有任何面额，只有金额零有一种“不取硬币”的空组合，所以 dp[0] = 1，其余为零。

加入当前面额后，金额 i 的组合分成两类：不使用当前面额的方案保留原来的 dp[i]；至少使用一枚当前面额的方案，可以先拿出其中一枚，剩下的就是金额 i - coin 的组合，并且仍然允许使用当前面额。因此转移为 dp[i] += dp[i - coin]。

金额必须从小到大更新。读取较小的 dp[i - coin] 时，它已经包含本轮使用当前面额的方案，再追加一枚就允许重复使用这个面额。如果从大到小更新，读取的全部是上一轮状态，当前面额就最多只能使用一枚。

面额放在外层，是为了让每种组合只有一条计数路径：先确定仅由前面面额组成的组合，再逐步加入当前面额的枚数，不再把不同取币顺序分开统计。每个含当前硬币的组合，去掉一枚后唯一对应一个前驱组合；与不含当前硬币的那类也不重叠，因此转移既不遗漏也不重复。

每次相加后立即取模，控制计数大小。处理完四种面额后，dp[n] 就是允许所有硬币时的组合数；金额为零时，空组合仍是唯一方案。

解题步骤

  1. 创建 n + 1 项计数数组，初始化 dp[0] = 1。
  2. 外层按固定顺序枚举四种面额。
  3. 内层从 i = coin 到 n 递增，执行 dp[i] = (dp[i] + dp[i - coin]) % MOD。
  4. 所有面额处理完后返回 dp[n]。

代码实现

class Solution {
    private static final int MOD = 1_000_000_007;

    public int waysToChange(int n) {
        int[] coins = {
            1,
            5,
            10,
            25
        };
        int[] dp = new int[n + 1];

        // 空组合是所有新增硬币方案的起点。
        dp[0] = 1;

        // 固定面额顺序，避免重复计算不同取币排列。
        for (int coin : coins) {
            // 金额正序读取本轮新值，允许同一面额继续使用。
            for (int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % MOD;
            }
        }

        return dp[n];
    }
}

func waysToChange(n int) int {
    coins := []int{
        1,
        5,
        10,
        25,
    }
    const mod = 1000000007

    dp := make([]int, n+1)
    // 空组合是所有新增硬币方案的起点。
    dp[0] = 1

    // 固定面额顺序，避免重复计算不同取币排列。
    for _, coin := range coins {
        // 金额正序读取本轮新值，允许同一面额继续使用。
        for i := coin; i <= n; i++ {
            dp[i] = (dp[i] + dp[i-coin]) % mod
        }
    }

    return dp[n]
}

复杂度分析

  • 时间复杂度：$O(n + 1)$，固定四种面额，每种最多扫描全部金额状态，初始化也需要线性时间。
  • 空间复杂度：$O(n + 1)$，只保存一维金额计数数组，无须记录具体取币组合。

关键点总结

[!green]

  • 外层面额固定组合的分类顺序，避免按不同取币先后重复计数。
  • 内层金额递增读取本轮状态，允许当前面额重复使用。
  • 不用当前面额和至少用一枚当前面额，是互不重叠的两类方案。

易错点总结

[!yellow]

  • 把金额放到外层、面额放到内层，会按最后一枚硬币区分取币顺序，统计成排列数。
  • 金额倒序更新，会把每个面额限制为至多一枚，变成另一种背包问题。
  • 忘记 dp[0] = 1，就没有空组合可用于加入第一枚硬币，所有正金额都无法产生方案。
  • 直接覆盖 dp[i] 而不是累加，会丢掉不使用当前面额的旧方案。
  • 延迟到最后才取模，计数增长可能在此前就超出整数范围，应每次转移取模。

相似题目

题目 难度 关联与区别
322. 零钱兑换 中等 候选硬币都可重复使用，原题求最少枚数，本题统计不区分顺序的组合数。
377. 组合总和 Ⅳ 中等 两题都计数，但原题不同排列顺序算不同方案，循环顺序不能混用。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/57613487
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！