LeetCode 面试题 08.11. 硬币

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

题目描述

✅ 面试题 08.11. 硬币

题意分析

面额固定为 1、5、10、25 四种，每种可以无限使用，问凑出金额 n 有多少种方式，结果对 $10^9 + 7$ 取模。

「要取模」这一条本身就是最强的信号：它说明答案是个天文数字，因此不可能靠枚举所有方案来数，只能用递推把方案数累加出来。n 的上界是 $10^6$，进一步限定了可接受的量级——线性或者常数倍线性的递推可以，任何随 n 呈平方增长的做法都会超时。

另一个必须先看清的点是：要数的是组合，不是排列。硬币没有顺序，25 + 1 与 1 + 25 是同一种凑法，只能算一次。这个区别不会体现在状态定义上，只会体现在递推的顺序上，是本题唯一真正的坑。

边界：n = 0 时答案是 1，即「一枚都不拿」也算一种凑法；n < 5 时只有全用 1 元这一种。

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

核心思路

因为面额只有四种，最朴素的写法是三重循环枚举 25、10、5 各用几枚，剩下的用 1 补齐。它的正确性没问题，但循环次数是 $\frac{n}{25} \times \frac{n}{10} \times \frac{n}{5}$，n 取 $10^6$ 时是 $3 \times 10^{15}$ 量级，直接出局；而且这个写法完全依赖「面额只有四种」，换成任意面额就写不出来了。

递推的自然想法是 f(i) = f(i-1) + f(i-5) + f(i-10) + f(i-25)，可它数出来的是排列数：f(6) 会同时从 f(5) 加一枚 1 和从 f(1) 加一枚 5 得到，而这两条路径拼出的其实是同一个多重集合。瓶颈就在这里——同一个组合被不同的凑取顺序重复计数了。

消除重复的标准办法是给每个组合规定唯一的书写顺序：规定必须先决定用几枚 1，再决定几枚 5，然后 10，最后 25。这样一来，每个组合与「按面额下标从小到大做决策的路径」一一对应，重复自然消失。

把这句话翻译成状态定义：dp[j][i] 表示只允许使用前 j 种面额时，凑出金额 i 的组合数。转移分两种决策——第 j 种面额一枚都不用，方案数是 dp[j-1][i]；至少用一枚，剩下 i - coins[j] 仍然允许继续使用第 j 种，方案数是 dp[j][i - coins[j]]。第二项引用的是同一行而不是上一行，这正是「无限次使用」在公式里的样子。

第一维可以滚动掉。外层按面额循环、内层金额从小到大递增时，dp[i - coin] 读到的已经是本轮更新过的新值，恰好等于二维式子里的 dp[j][i - coin]；而 dp[i] 在被写入之前保存的还是上一轮的值，正是 dp[j-1][i]。于是 dp[i] += dp[i - coin] 这一行同时完成了两种决策的求和。

循环不变量：外层第 j 轮结束后，dp[i] 恒等于「只用前 j 种面额凑出金额 i 的组合数」。初值 dp[0] = 1 表示空组合，它不是为了避免除零之类的补丁，而是「凑出 0 元有且只有一种方式」这一事实。

解题步骤

  • 准备面额数组与 dp 数组：coins = {1, 5, 10, 25}，dp 长度取 n + 1，因为金额 0 到 n 都要有位置。
  • dp[0] = 1，其余为 0：其余为 0 的含义是「在还没考虑任何面额时，除了 0 元，别的金额都凑不出来」，这与不变量在 j = 0 时的表述一致。
  • 外层遍历面额：面额必须在外层。它就是上面那条「唯一书写顺序」的实现，一旦挪到内层就变成数排列。
  • 内层金额从 coin 递增到 n：起点取 coin 而不是 0，是因为金额小于面额时这枚硬币根本用不上，dp[i - coin] 也会越界；递增而不是递减，是因为要允许同一面额被重复使用（递减是 01 背包的写法，会把每种硬币限制成最多一枚）。
  • 累加并取模：dp[i] = (dp[i] + dp[i - coin]) % MOD。取模要贴着累加做，方案数在 n 较大时远超 32 位。
  • 返回 dp[n]：此时外层四轮都跑完，按不变量它就是允许使用全部四种面额时的组合数。

以 n = 10 走一遍（答案应为 4：十枚 1、五枚 1 加一枚 5、两枚 5、一枚 10）：

  • 初始：dp = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  • coin = 1 跑完：dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]，含义是只用 1 元时每个金额都恰好一种凑法
  • coin = 5 时，i = 5 处 dp[5] += dp[0] 得 2；i = 6..9 各自加上 dp[1..4] 都变成 2；i = 10 处 dp[10] += dp[5]，读到的 dp[5] 已是本轮的新值 2，于是 dp[10] = 1 + 2 = 3。跑完得 dp = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3]
  • coin = 10 时只有 i = 10 进循环：dp[10] += dp[0]，得 4
  • coin = 25 时 25 > 10，内层一次都不进，dp 不变
  • 返回 dp[10] = 4

注意 i = 10、coin = 5 那一步：读到的 dp[5] = 2 里已经包含了「一枚 5」，配上当前这枚 5 得到「两枚 5」；如果内层递减，读到的就是旧值 1，「两枚 5」这种凑法会被漏掉。

反过来把两层循环调换（外层金额、内层面额），同样是 n = 10，递推变成 f(i) = f(i-1) + f(i-5) + f(i-10)，算出的是 f(10) = f(9) + f(5) + f(0) = 6 + 2 + 1 = 9——多出来的 5 种全部是顺序不同、内容相同的重复计数。

代码实现

class Solution {
    // 用完全背包的一维 DP：dp[i] 表示凑出金额 i 的方案数，dp[0] = 1 表示什么都不选也是一种基础方案。
    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 {
    // 用完全背包的一维 DP：dp[i] 表示凑出金额 i 的方案数，dp[0] = 1 表示什么都不选也是一种基础方案。
    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)$，外层是 4 次固定循环，内层至多 n 次，总操作数不超过 $4n$，面额种数是常数所以不进渐进式。
  • 空间复杂度：$O(n)$，只保留滚动后的一维数组，长度为 n + 1；二维写法的 $O(4n)$ 被压掉了一维，代价是必须把内层顺序写对。

关键点总结

  • 组合还是排列，完全由两层循环的顺序决定：面额在外层数的是组合，金额在外层数的是排列。这是完全背包计数类问题被追问得最多的一句话，答不上来基本就废了。
  • 完全背包内层正序、01 背包内层倒序。正序意味着 dp[i - coin] 已经包含了当前面额，等价于「这枚硬币可以再拿一次」；能讲出这层等价关系，比背口诀有用得多。
  • dp[0] = 1 是空组合的语义，不是边界补丁。凡是计数型 dp，先想清楚「什么都不选」算不算一种方案。
  • 面试时先写二维状态定义和转移，再当场压成一维，能直接证明你知道一维是怎么来的；上来就写一维，很容易在被追问循环顺序时讲不清。
  • 取模贴着累加做，别攒到最后。方案数增长极快，晚一步就已经溢出了。

易错点总结

  • 外层枚举金额、内层枚举面额：n = 10 时返回 9 而不是 4，多出来的都是顺序不同的重复方案。这是本题第一大错误。
  • 内层倒序（照抄 01 背包）：n = 10 时每种面额最多被用一次，只剩「一枚 10」这一种，返回 1。
  • 内层起点写成 0 或 1：i = 0、coin = 5 时访问 dp[-5]，直接抛数组越界异常。
  • dp 数组开成 new int[n]：n = 1000 时最后一句 dp[n] 越界。
  • 忘记 dp[0] = 1：整张表恒为 0，任何 n 都返回 0。
  • 只在返回时取模：n = 1000000 的中间结果远超 int 上界，累加过程中就已经回绕成负数，最后取模得到负值。
  • 把状态定义记成「最少硬币数」（与 322 零钱兑换记混）：n = 10 会返回 1，而题目要的是方案数 4。
  • 写成递归枚举每一枚硬币：n = 1000000 时递归深度就有 $10^6$，分支数更是爆炸，必然栈溢出或超时。
  • 以为面额数组必须先排序：写成 {25, 10, 5, 1}，n = 10 同样返回 4——组合数与面额的枚举顺序无关，把「必须升序」当前提会在别的背包题里误导自己。

相似题目

题目 难度 考察点
518. 零钱兑换 II 中等 与本题同型的组合计数，面额改由入参给出，本题则写死为四种
322. 零钱兑换 中等 同样是完全背包但求最少硬币数，初值改成无穷大、转移由求和变取 min
377. 组合总和 Ⅳ 中等 要的恰恰是排列数，正好把本题两层循环的顺序调过来
279. 完全平方数 中等 面额是 1、4、9…… 由 n 现场生成，且求的是最少个数
416. 分割等和子集 中等 01 背包，每个数只能用一次，内层必须倒序，是本题正序的反面教材
1449. 数位成本和为目标值的最大数字 困难 恰好装满的完全背包，价值不是计数而是字符串大小，比较规则要自定义
LCR 103. 零钱兑换 中等 与 322 同题，可直接套用
LCR 104. 组合总和 Ⅳ 中等 与 377 同题，可直接套用