LC322　零钱兑换¶

中等通过率 53.3%python3核心代码模式动态规划样例通过牛客 AC广度优先搜索数组动态规划背包问题完全背包

牛客原题　源码

讲解章节：背包问题

一句话

面值无限供应的完全背包求最少枚数，容量正序推，凑不出返回 -1。

解题思路¶

这题考什么¶

「每种硬币可以取任意多枚，凑出总额所需的最少枚数」是完全背包的最小化形态，见背包问题。

状态定义：f[c] 表示凑出金额 c 所需的最少硬币枚数。转移方程（v 遍历每种面值）：

f[c] = min(f[c], f[c - v] + 1)        c 从 v 到 amount，**正序**

初值 f[0] = 0（凑 0 元一枚不用），其余取一个达不到的大数当无穷。

容量正序遍历是这题的核心，必须讲透：扫到 f[c] 时，f[c - v] 有可能 已经在本轮被同一个面值 v 更新过，于是「在那基础上再放一枚 v」这件事被自然允许，同一种硬币可以取任意多枚。若改成倒序，f[c - v] 一定还是「尚未考虑 v」的旧值，每种硬币就只能用一次，求出来是 01 背包的答案。这与 LC416 分割等和子集恰好相反——那题要的正是「每个数只用一次」，所以必须倒序。

为什么贪心不成立：直觉上「每次尽量用最大的面值」看似合理，但 coins = [1, 3, 4]、amount = 6 时贪心得到 4 + 1 + 1 = 3 枚，最优是 3 + 3 = 2 枚。只有当面值满足特殊的整除结构（如人民币）时贪心才对，一般面值下必须 DP。

数据规模与复杂度¶

1 <= coins.length <= 12，1 <= coins[i] <= 2^31 - 1，0 <= amount <= 1e4。时间 O(面值数 * amount) = 12 * 1e4 = 1.2e5 次内层迭代，毫秒级。空间 O(amount)，一个长度 amount+1 的整数列表。

面值上界 2^31 - 1 远大于金额上界 1e4，这个反差是题面刻意设的：比 amount 还大的硬币一枚也放不进去，先滤掉可以省掉一整轮空转的 range。

坑在哪¶

无解要返回 -1，不能返回哨兵值。用 amount + 1 当「无穷」，是因为全用面值 1 也至多需要 amount 枚，任何真实答案都不会超过 amount，所以末尾判 f[amount] > amount 即无解。取整数哨兵而不是 float('inf')，既保持整数运算，又让这条判据自然成立。
amount = 0 要返回 0（题面样例 3 明确要求）。f 只有 f[0] = 0 一项，所有面值都因 v > 0 而使内层 range 为空，直接返回 f[0] = 0，无需特判。
内层容量必须正序。倒序会退化成每种硬币只用一次： coins = [1, 2, 5]、amount = 11 时子集和最大是 8，凑不出 11， f[11] 停在哨兵上，函数返回 -1，而正确答案是 3。
滤掉 v > amount 属于优化而非正确性要求：不滤时 range(v, amount + 1) 为空，结果照样对。但面值可以大到 2^31 - 1，为一枚放不进去的硬币白建一次空区间纯属浪费，显式跳过也让「大面值不参与转移」这件事在代码里看得见。
题面没有保证 coins 内的面值互不相同，也没保证有序。这份写法对重复面值免疫（同一面值多推一轮不改变结果），顺序也无关，所以不需要预先去重或排序。

样例复核¶

coins = [1, 2, 5]，amount = 11。

只用 1：f[c] = c，f[11] = 11
加入 2 正序扫：f[2] = 1, f[4] = 2, ..., f[10] = 5, f[11] = f[9] + 1 = 5 + 1 = 6
加入 5 正序扫：f[5] = f[0] + 1 = 1，f[6] = f[1] + 1 = 2（即 5 + 1），
               f[10] = f[5] + 1 = 2（即 5 + 5），
               最后 f[11] = f[6] + 1 = 3。
               f[6] 是在**本轮内**被压到 2 的，f[11] 立刻用上了这个新值——
               这就是正序遍历让同一面值被重复取用的具体样子

返回 3，对应 5 + 5 + 1，与期望输出一致。

参考实现¶

solutions/leetcode/LC322/sol.py
from typing import List, Optional


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 「无穷」取 amount + 1：全用面值 1 至多要 amount 枚，真实答案绝不会到这个数，
        # 于是它既是安全哨兵，又让末尾「大于 amount 即无解」这条判据自然成立
        f = [0] + [amount + 1] * amount     # f[c] = 凑出金额 c 的最少枚数，f[0] = 0 是起点
        for v in coins:
            # 面值可以大到 2^31-1，比总额还大的硬币一枚也放不进，直接跳过省一轮空转
            if v > amount:
                continue
            # 完全背包的标志是容量**正序**：扫到 f[c] 时 f[c-v] 可能已在本轮被同一面值
            # 更新过，于是同一种硬币允许取任意多枚。倒序则 f[c-v] 必是旧值，
            # 退化成每种硬币只用一次的 01 背包，coins=[1,2,5]、amount=11 会错判无解
            for c in range(v, amount + 1):
                if f[c - v] + 1 < f[c]:
                    f[c] = f[c - v] + 1
        # 没被任何转移压下来的格子仍停在哨兵上，说明这个金额凑不出，按题意返回 -1
        return f[amount] if f[amount] <= amount else -1

LC322 零钱兑换¶