LeetCode 322. 零钱兑换：动态规划入门的第一道正餐

题目与为什么它是 DP 正餐

LeetCode 322「零钱兑换」的题面：给定硬币面额数组 coins 和目标金额 amount，每种面额可以无限次使用，求凑出目标金额所需的最少硬币数；凑不出来返回 -1。例如 coins = [1, 2, 5]、amount = 11，最少用 3 枚：5 + 5 + 1。

直觉解法是贪心——每次优先用最大面额。它在这题恰好是错的：coins = [1, 3, 4]、amount = 6，贪心给出 4 + 1 + 1 共 3 枚，而最优解是 3 + 3 共 2 枚。局部最优拼不出全局最优，这正是需要动态规划（Dynamic Programming，简称 DP：把大问题拆成同构的小问题，把小问题的答案存表复用）的信号。

这道题适合作为 DP「第一道正餐」的原因，在于它同时具备教科书式的两个要件。一是最优子结构：凑出金额 i 的最优方案里，「最后一枚硬币」选 coin 时，剩下的 i - coin 也必须是凑法最优的，否则整体可以被替换得更优。二是重叠子问题：计算 dp[6] 与 dp[5] 都会用到 dp[3]，存表就能避免重复计算。此外它还是「完全背包」（每种物品可无限量选取的背包问题）在最小化目标下的变体，学会它能顺带打通一整族题目。

状态设计与转移

定义 dp[i] 为凑出金额 i 所需的最少硬币数。转移方程：枚举最后一枚硬币的面额 coin，dp[i] = min(dp[i - coin] for coin in coins) + 1。

这个状态设计的巧思在于把「用了多少硬币」藏进了递推路径：dp 只按金额开维度，硬币数天然等于「递推走了几步」，不必作为额外维度记录——状态里只放对后续决策有影响的量，这是设计状态的第一原则，本题正是它的最小示范。

以 coins = [1, 2, 5] 为例从 0 往上填表：dp[1] = dp[0] + 1 = 1；dp[2] 可以由 dp[1] 加一枚 1、也可以由 dp[0] 加一枚 2，取最小得 1；dp[3] = dp[1] + 1 = 2（1+2 或 1+1+1）；到 dp[5] 时 dp[0] + 1 = 1，一枚 5 直达。每个位置只看「比它小的、已经算好的位置」，这正是自底向上顺序的保证。

初始化有两处关键：dp[0] = 0——凑 0 元不需要硬币，它也是全部递推的地基；其余位置初始化为一个「无穷大」哨兵，表示「暂时凑不出」。哨兵取 amount + 1 即可：每枚硬币面额至少为 1，凑出任何可达金额所需的硬币数不会超过 amount，所以 amount + 1 能安全充当无穷大，最后判断也只需与 amount 比大小。

参考实现

def coinChange(coins, amount):
    dp = [0] + [amount + 1] * amount          # dp[0]=0，其余为哨兵
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] <= amount else -1

这份自底向上的写法，与记忆化递归（递归求解 f(i)，把算过的结果缓存起来备用）在数学上完全等价：前者按金额从小到大填表，后者从 amount 向下递归、遇缓存即返回。求最小值的场景没有后效性顾虑，两种写法选顺手的即可。

三个易错点

无解判断。若哨兵位置从未被更新就直接返回，会把「凑不出」错误地当成一个巨大数字返回，必须先判断再返回。测试用例 coins = [2]、amount = 3 专门卡这一点。
重复面额。题目不保证 coins 内元素互不相同。写法上要么容忍重复（同一面额多比一次无害，只是多算一遍），要么先去重，别在判重上想当然。
内外层循环顺序。本题「先金额后硬币」与「先硬币后金额」结果一致——求最小值与硬币选取顺序无关。但到了计数类题目（如 LeetCode 518 求组合数），先硬币后金额数的是「组合」、先金额后硬币数的是「排列」，两者答案不同。记住这个分界线，比记住单题写法更有价值。

复杂度与延伸

时间复杂度 O(amount × n)，n 是面额种数：金额表每个位置都要枚举一遍所有面额。空间复杂度 O(amount)。

换个视角会豁然开朗：把 0 到 amount 的每个金额看成图上的节点，金额 i 与 i + coin 之间连一条有向边，权为 1。「最少硬币数」就是从 0 到 amount 的最短路边数，用 BFS（广度优先搜索：从起点逐层向外扩散，首次到达某节点时的层数即最短距离）求解同样正确。DP 与最短路在此打通：这个 DP 本质上就是在无权图上做逐层松弛，两种视角互为印证。两种解法访问的状态集合完全相同，都是 O(amount × n) 量级；DP 胜在代码更短、常数更小，BFS 胜在思路更直观——面试时能说清两者等价，比只会其中一种更加分。

要点小结

最少硬币数满足最优子结构与重叠子问题，是完全背包的最小化变体。
转移 dp[i] = min(dp[i - coin]) + 1；初始化 dp[0] = 0、其余哨兵；返回前先判断无解。
循环顺序在最小化题中无所谓，在计数类组合/排列题中有所谓。
BFS 视角：金额即节点，答案即最短路。