题目要求

给定一个整数数组 coins，其中 coins[i] 是一种硬币的面额；再给定一个非负整数 amount，要求凑出刚好等于 amount 的金额。

  • 每种硬币都可以使用任意次。
  • 返回凑出 amount 所需的最少硬币数量。
  • 如果无法凑出，返回 -1。
  • 如果 amount = 0，不需要使用硬币，答案是 0。

约束是：1 <= coins.length <= 12、1 <= coins[i] <= 2^31 - 1、0 <= amount <= 10^4。硬币面额互不相同。

例如：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：5 + 5 + 1 一共使用 3 枚硬币。

输入：coins = [2], amount = 3
输出：-1
解释：只使用面额 2 无法凑出 3。

输入：coins = [1], amount = 0
输出：0
解释：目标金额已经是 0，不需要再选硬币。

Step 1：先把目标金额拆成更小的问题

先看一个会逼出问题结构的小例子：

coins = [1, 3, 4]
amount = 6

如果只凭“优先拿更大面额”的直觉，可能先拿 4，剩下 2，最后得到 4 + 1 + 1，一共 3 枚硬币。但更好的方案是 3 + 3，只需要 2 枚。

当前 baseline 是“每次挑一枚看起来大的硬币”，它在这个例子上失败：同一个目标金额存在不同组合，局部较大的面额不保证总枚数最少。

这个 break 逼出一个具体问题：如果最后选的是某一枚硬币，剩下的金额是多少？我们必须比较不同的最后一枚硬币；选定一枚之后，剩下的金额又是一个更小、形式相同的问题。

本步只加入这个较小的问题定义，先记成：

best(x) = 凑出金额 x 所需的最少硬币数

这一步只是在明确要反复询问什么。现在还没有定义 best(0) 的完成条件，也没有写出如何从 best(x - coin) 得到 best(x) 的转移。

检查这一步：4 + 1 + 1 使用 3 枚，3 + 3 使用 2 枚；因此只看单次选币无法得到答案，必须继续处理剩余金额。

当前版本能做到：

  • 说清楚输入、输出和“每种硬币可重复使用”的边界。
  • 用 [1, 3, 4], 6 证明直接贪心不够。
  • 把大金额问题改写成“先理解更小金额”的问题。

它还缺：

  • 金额为 0 时什么时候停止。
  • 正金额如何尝试每一种硬币并比较结果。

Step 2：先处理金额 0

先问一个更小的问题：如果还需要凑出的金额已经是 0，还要再拿几枚硬币？答案不是“无法凑出”，而是 0 枚。这个完成条件必须先固定下来，后面的每条选币路径才知道什么时候结束。

当前 baseline 是上一节定义的 best(x)，但它还没有任何停止规则。它会在 x = 0 时失去含义；如果连这个最小金额都没有答案，正金额的处理也无法接上。

在上一版的 best(x) 上，只加入金额为 0 的分支：

def best(x: int) -> int:
    if x == 0:
        return 0

    raise NotImplementedError("正金额的候选将在下一步加入")

这里的 raise 是刻意留下的缺口：本步只验证完成条件，不假装已经解决正金额。

检查这一步：把 x = 0 代入，函数直接返回 0；把 x = 1 代入，则明确暴露“正金额还没有候选转移”，不会把一个临时数字误当成答案。

现在这个版本能做到：

  • 明确 best(0) = 0，表示目标已经完成。
  • 把正金额分支和完成条件分开，后续可以在缺口处接入选币逻辑。

它还缺：

  • 对 x > 0，如何逐个尝试不超过 x 的硬币。
  • 每个候选如何接回另一个更小金额的 best。

Step 3：枚举最后一枚硬币，先得到一个正确版本

现在要填上的缺口是：对正金额 x，最后一枚硬币可能是 coins 中的任意一种。选了 coin 之后，前面还需要凑出 x - coin；如果这个更小金额能凑出，就在它的硬币数上再加 1。

当前 baseline 是上一节的 best(x)：它已经知道 x = 0 时返回 0，但 x > 0 会直接抛出异常。这个 break 很具体：没有候选转移，任何正金额都无法回答。

在上一版的 best 函数中，替换掉 NotImplementedError，加入“尝试每枚硬币并取最小值”的逻辑：

def coin_change_recursive(coins: list[int], amount: int) -> int:
    def best(x: int) -> int:
        if x == 0:
            return 0

        minimum = float("inf")
        for coin in coins:
            if coin > x:
                continue

            rest = best(x - coin)
            if rest == -1:
                continue

            minimum = min(minimum, rest + 1)

        return -1 if minimum == float("inf") else minimum

    return best(amount)

这里的 minimum 只是当前 x 的候选最小值；float("inf") 表示“到目前为止还没有找到可达方案”。只有递归结果不是 -1 时，才把当前硬币计入候选。

检查这一步：对 coins = [1, 3, 4]、amount = 6，最后一枚取 4 时，剩余 2 至少需要 2 枚，于是这一分支共 3 枚；最后一枚取 3 时，剩余 3 只需要 1 枚，于是这一分支共 2 枚，函数会保留后者。运行小例子还应得到：

[1, 2, 5], 11 -> 3
[2], 3 -> -1

现在这个版本能做到：

  • 对每个正金额尝试所有合法的最后一枚硬币。
  • 正确处理更小金额无解的分支。
  • 在小规模输入上得到第一个完整、正确的答案。

它还缺：

  • 同一个 best(x) 会从不同路径被反复计算。
  • 金额较大时，递归树会迅速变大，当前版本只是正确 baseline，不是最终复杂度。

Step 4：缓存已经求过的金额

先看 Task 3 的递归会怎样重复询问金额。对 [1, 3, 4]、6，一条路径会出现 best(6) -> best(5) -> best(2)，另一条路径也会出现 best(6) -> best(3) -> best(2)。两条路径对 best(2) 的答案完全相同，却会把同一棵子树再算一遍。

当前 baseline 是“转移正确的递归版本”；它的 break 不是答案错误，而是重复工作：金额越大，重复的递归分支越多。

在上一版的 best 定义前只加入一个按金额缓存的装饰器，函数内部的候选转移保持不变：

from functools import cache


def coin_change_memo(coins: list[int], amount: int) -> int:
    @cache
    def best(x: int) -> int:
        if x == 0:
            return 0

        minimum = float("inf")
        for coin in coins:
            if coin > x:
                continue

            rest = best(x - coin)
            if rest == -1:
                continue

            minimum = min(minimum, rest + 1)

        return -1 if minimum == float("inf") else minimum

    return best(amount)

缓存的键只有金额 x：同一个 x 的最少硬币数不会因为到达路径不同而改变。于是最多只会有 amount + 1 个不同金额状态被求解，原来的“每条路径都重算”被压成“每个状态一次”。

检查这一步：用同一组输入运行缓存版本，答案仍应是 [1, 2, 5], 11 -> 3、[2], 3 -> -1、[1, 3, 4], 6 -> 2，并检查每组的状态数不超过 amount + 1。对于确实包含重复子问题的 [1, 3, 4], 6，再查看 cache_info()，命中次数应大于 0；像 [2], 3 这种只走一条失败路径的输入，命中为 0 也符合预期。

现在这个版本能做到：

  • 保留 Task 3 的正确转移和无解处理。
  • 对同一个金额只保留一份递归结果，状态数量至多为 amount + 1。

它还缺：

  • 递归调用栈仍然随金额增长。
  • 还没有把同一转移改写成从小金额到大金额的迭代表格。

Step 5：把递归改成从小到大的表

Task 4 已经证明：每个金额状态只需要求一次。但它仍然通过函数调用向下追问，金额很大时，调用栈本身就会成为负担。

当前 baseline 是带缓存的 best(x)。它的 break 不是状态含义不清，而是状态仍藏在递归调用里；我们需要让“金额 0 到 amount 的每个结果”显式排成一张表。

在上一版的候选转移基础上，只把“递归得到更小金额”替换成已填好的 dp 表：

def coin_change_table(coins: list[int], amount: int) -> int:
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0

    for x in range(1, amount + 1):
        for coin in coins:
            if coin > x or dp[x - coin] == float("inf"):
                continue

            dp[x] = min(dp[x], dp[x - coin] + 1)

    return -1 if dp[amount] == float("inf") else dp[amount]

这里的状态含义是：dp[x] 表示“刚好凑出金额 x 所需的最少硬币数”；dp[0] = 0 延续了上一节已经验证过的完成条件；其余位置先用无穷大表示“当前还没有找到方案”。处理 x 时，所有更小的 dp[x - coin] 都已经填好。

用 coins = [1, 2, 5]、amount = 11 慢速走表，得到：

x01234567891011
dp[x]011221223323

所以 dp[11] = 3。这张表是递归版本的同一条转移，只是把“调用更小金额”改成“读取已经完成的表项”。

检查这一步：运行表版本应得到 [1, 2, 5], 11 -> 3、[2], 3 -> -1、[1], 0 -> 0 和 [1, 3, 4], 6 -> 2，并且 [1, 2, 5], 11 的整张表与上面的手算一致。

现在这个版本能做到：

  • 用一个显式数组保存每个金额的最优值。
  • 在不依赖递归调用栈的情况下得到第一个完整的迭代正确版本。

它还缺：

  • 为什么金额要按正序处理，以及这如何体现“同一种硬币可以使用任意次”。
  • “完全背包”这个名称与当前更新顺序之间的对应关系。

Step 6：为什么这是完全背包

现在看一个不能回避重复使用的例子：

coins = [2]
amount = 6

答案必须是 2 + 2 + 2，也就是 3 枚同样的硬币。当前 baseline 的 dp[x] 转移已经能表达这个答案，但还没有解释：为什么更新顺序允许刚刚用过的 2 再用一次？如果把它误当成“每种硬币只能选一次”的 0/1 问题，就会漏掉 4 和 6 这些连续状态。

这个 break 逼出遍历顺序的含义：处理面额 coin 时，金额必须从小到大走。这样算出 dp[2] = 1 后，继续算 dp[4] 时可以读取这个已经包含当前面额的状态；再算 dp[6] 时又可以读取 dp[4]。

在上一版表格代码中，替换两个循环的组织方式，让“每种硬币可无限次使用”显式可见：

def coin_change_complete(coins: list[int], amount: int) -> int:
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for x in range(coin, amount + 1):
            if dp[x - coin] == float("inf"):
                continue

            dp[x] = min(dp[x], dp[x - coin] + 1)

    return -1 if dp[amount] == float("inf") else dp[amount]

对 [2]、6 的更新轨迹是：x = 2 时 dp[2] = 1，x = 4 读取 dp[2] 得到 dp[4] = 2，x = 6 再读取 dp[4] 得到 dp[6] = 3。这就是“完全背包”：一个物品（这里是一种面额）可以被取任意次，所以内层金额使用正序。0/1 背包则要用倒序，避免同一轮再次读到当前物品；两者的方向不能混用。

本题优化目标是“最少数量”，不是“不同排列的数量”。因此这里每次只做 min，不会因为 2 + 5 和 5 + 2 的顺序不同而把答案重复计数。

检查这一步：运行新循环应得到 coins = [2], amount = 6 -> 3，以及 coins = [2, 3, 5], amount = 7 -> 2；前面三个官方/压力例子的答案也应保持不变。

现在这个版本能做到：

  • 把“可重复使用”落实为硬币外层、金额正序的完全背包更新。
  • 解释为什么 dp[x - coin] 可以来自本轮已经更新的状态。
  • 保持求最少数量，而不是改成排列计数。

它还缺：

  • LeetCode class Solution 的最终接口。
  • 统一的不可达返回、正确性不变量和复杂度收束。

Step 7：冻结最终实现

前一节已经把“硬币可以重复使用”落实为硬币外层、金额正序内层；现在只做交付层收束：把同一段逻辑放进 LeetCode 要求的 class Solution，并把无解的无穷大转换成 -1。这里不再引入新的状态或转移。

当前 baseline 是 coin_change_complete 的可运行函数。它的 break 是接口还不能直接提交，而且需要把 amount = 0、无解金额和普通金额的返回约定放到同一个方法里。

把上一版函数整合成唯一的最终代码：

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        unreachable = amount + 1
        dp = [unreachable] * (amount + 1)
        dp[0] = 0

        for coin in coins:
            for current in range(coin, amount + 1):
                dp[current] = min(dp[current], dp[current - coin] + 1)

        return -1 if dp[amount] == unreachable else dp[amount]

unreachable = amount + 1 是一个足够大的有限哨兵：任何可行方案至多使用 amount 枚面额至少为 1 的硬币，所以它不会与合法答案混淆。dp[0] = 0 仍是已审查的完成条件；每次更新仍读取当前面额在本轮正序更新过的 dp[current - coin]，因此无限复用语义没有改变。

正确性可以沿着一个不变量检查：处理完某个 coin 后，对每个 current，dp[current] 是只使用已经处理的面额、且每种面额可重复使用时凑出 current 的最少硬币数；正序扫描让当前面额可以再次接到本轮刚得到的更小金额结果上。处理完全部硬币后，dp[amount] 就是题目要求的最少数量；若仍为哨兵，则没有任何组合能凑出目标金额，返回 -1。

复杂度：状态数是 amount + 1，每个状态最多被每种硬币检查一次，因此时间复杂度为 O(amount * len(coins))，额外空间复杂度为 O(amount)。

边界回归：

coins = [1, 2, 5], amount = 11 -> 3
coins = [2], amount = 3 -> -1
coins = [1], amount = 0 -> 0
coins = [2], amount = 6 -> 3
coins = [1, 3, 4], amount = 6 -> 2

现在这个版本能做到：

  • 直接符合 LeetCode 的 class Solution 方法契约。
  • 覆盖可达、不可达、零金额和同一面额重复使用的边界。
  • 让最终代码、正确性说明和复杂度都来自前面已经审查过的 checkpoint。

本题的增量构建到这里冻结；不再追加会引入新逻辑的 Reference Answer。