硬币凑钱算是我这几年在面试和实际开发里都反复遇到的一个问题，表面上看是个入门级动态规划，可一旦你把它和完全背包联系起来，思路一下就通透了。这篇文章我会从模型推导、代码实现、变式扩展三个角度拆透这个经典问题，顺便把我踩过的一些坑和排查心得一并分享出来。
1. 问题定义与核心思路
1.1 两种最常见的问法
硬币凑钱（Coin Change）在 LeetCode 上是 322 和 518 两道题，前者问“凑成指定金额最少需要几枚硬币”，后者问“有多少种不同的凑法”。虽然题目只差几个字，背后的状态定义和转移方程完全不同，但都属于同一类完整背包变式。
- 最少硬币数：给定不同面额的硬币 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币个数。如果没有任何一种组合能凑出，返回 -1。
- 凑法总数：给定不同面额的硬币和一个总金额，计算凑成总金额的硬币组合数。每种面额使用次数不限，组合不区分顺序。
这两个问题都是经典的“选或不选”决策问题，而且每个硬币可以选择多次，这正好命中完全背包的特征。
1.2 为什么是“完全背包的变式”
标准的完全背包描述是：有一个容量为 V 的背包，n 种物品，每种物品无限供应，第 i 种物品体积 w[i]、价值 v[i]，问能装入的最大价值。
硬币凑钱问题换个说法就完全对上了：背包容量就是目标金额 amount，每个硬币的面额就是物品体积，所有硬币的价值统一为 1（求最少个数时）或者说“方案数”（求凑法总数时）。这样一来，完全背包的状态定义、初始化方式、转移方向，全都能平移过来。
注意：硬币凑钱和标准完全背包最大的区别在于“价值不是累积的”，而是求极值或计数。所以转移方程里不是 max 前一个价值和加入当前物品后的价值，而是把价值换成硬币个数或组合数。
1.3 一套模板吃透所有变式
我自己的经验是，把动态规划写成一套模板，根据题目改状态转移和初始化就行，不要每次从零推。下面这个伪代码框架可以应对最少硬币数、凑法总数、能否凑出等多种变式：
初始化 dp 数组，dp[0] = 一定是“空状态”的值 对于每个硬币面额 coin: 从小到大遍历金额 i 从 coin 到 amount: dp[i] = 结合当前硬币进行转移 返回 dp[amount]这个模板的核心就是从小到大遍历金额，这是完全背包和 01 背包在第二层循环方向上的关键差异。01 背包必须倒序遍历，防止同一个物品被重复使用；完全背包需要正序遍历，让同一个硬币可以反复取用。
2. 核心细节解析与实操要点
2.1 状态定义与转移方程
以“最少硬币数”为例，dp[i]表示凑成金额 i 所需的最少硬币数。初始时，dp[0] = 0，其余金额先设成一个足够大的数（比如float('inf')或amount + 1），表示暂时还未凑出。
状态转移逻辑是这样的：如果当前硬币面额是 coin，那么凑成金额 i 时，可以用一枚 coin 加上凑成i - coin的最优解，所以dp[i] = min(dp[i], dp[i - coin] + 1)。
def coinChange(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != amount + 1 else -1初始化时用amount + 1作为“不可能”标记，比用float('inf')更安全，因为前面提到过整数无限大容易溢出，而这个值即使加 1 也不会溢出，避免了一些诡异的 bug。从coin开始遍历也是刻意而为，小于一个硬币面额的金额不可能由这枚硬币组成，直接跳过可以节省不少无谓计算。
2.2 内层循环方向为什么必须正序
这是我见过最多人踩的坑。很多写过 01 背包的人一上来就用倒序遍历，结果最少硬币数算出来永远不对。
原因要从动态规划的覆盖顺序说。对于完全背包，我们希望同一枚硬币可以被多次使用，所以遍历金额时要从 coin 循环到 amount，这样在计算dp[i]时，dp[i - coin]可能已经包含了当前这枚硬币，也就是允许了重复选择。
for coin in coins: for i in range(coin, amount + 1): # 正序：完全背包如果改成倒序：
for coin in coins: for i in range(amount, coin - 1, -1): # 倒序：01背包那每一枚金币只能选一次，完全变成 01 背包的解法，对于 coins = [1, 2, 5], amount = 11 这种情况，输出就会偏大或直接错误。想检验自己是不是真的理解了，可以把上面两个循环都跑一遍，对比结果差异，印象会非常深刻。
2.3 初始化技巧与无解处理
dp[0] = 0这个初始状态是递推的基石，很多推导都依赖它。举一个简单例子：coins = [2, 3], target = 4，当 coin = 2 时，dp[2]会通过dp[0]转移得到 1；当 coin = 3 时，dp[3]依赖dp[0]得到 1。如果dp[0]不是 0 而是一个大数，整张 dp 表都会是错的。
无解判断也要小心。如果最终dp[amount]仍然是初始化的amount + 1，说明没有任何组合能凑出目标余额，此时应当返回 -1，而不是把amount + 1当成答案交出去。同样的逻辑也适用于“凑法总数”，不过那里用 0 当初始值，最终为 0 则说明没有可行组合。
2.4 空间复杂度优化路径
二维 DP 转一维 DP 是这类背包问题的常规优化。完整背包变式下，使用一维数组并用正序遍历，空间复杂度能从 O(n*amount) 降到 O(amount)，这在 amount 很大的时候非常关键。
理论上，二维数组在做状态转移时，dp[i][j]只依赖上一行和当前行之前的位置，所以滚动数组或一维覆盖都能正确完成。下面的代码是“最少硬币数”的一维优化版本，和前文完全一致，这也是面试时最常写的版本：
def coinChange(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return -1 if dp[amount] == amount + 1 else dp[amount]3. 实操过程与核心环节实现
3.1 用最少硬币案例推演整个 DP 过程
为了把原理说透，我拿 LeetCode 322 的官方样例 coins = [1, 2, 5], amount = 11 来完整推演一遍。
初始状态：
| 金额 i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| dp[i] | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
先处理 coin = 1，因为面额是 1，从 i=1 到 11 全部都能更新。dp[1] = dp[0] + 1 = 1，dp[2] = dp[1] + 1 = 2，以此类推，最后整行会变成[0, 1, 2, 3, ..., 11]。这符合直觉：全部用 1 元硬币的话，多少金额就需要多少枚。
再处理 coin = 2，从 i=2 开始：
- i=2：
dp[2] = min(2, dp[0]+1=1) = 1 - i=3：
dp[3] = min(3, dp[1]+1=2) = 2 - i=4：
dp[4] = min(4, dp[2]+1=2) = 2 - i=5：
dp[5] = min(5, dp[3]+1=3) = 3 - i=6：
dp[6] = min(6, dp[4]+1=3) = 3 - i=7：
dp[7] = min(7, dp[5]+1=4) = 4 - ...
可以看到，引入面额 2 后，相同金额能用更少的硬币表示。比如金额 4 以前要 4 枚 1 元，现在 2 枚 2 元就够了。
最后处理 coin = 5：
- i=5：
dp[5] = min(3, dp[0]+1=1) = 1 - i=6：
dp[6] = min(3, dp[1]+1=2) = 2 - i=7：
dp[7] = min(4, dp[2]+1=2) = 2 - i=8：
dp[8] = min(4, dp[3]+1=3) = 3 - i=9：
dp[9] = min(5, dp[4]+1=3) = 3 - i=10：
dp[10] = min(5, dp[5]+1=2) = 2 - i=11：
dp[11] = min(6, dp[6]+1=3) = 3
最终dp[11] = 3，最优组合是 5 + 5 + 1。这个结果和 LeetCode 官方答案一致。
整个过程的关键在于，每一轮 coin 的处理都建立在之前已经优化的基础之上。小面额硬币先打底，大面额硬币再优化结果，但这个“先小后大”的顺序并不是必须的，无论先处理 5 还是先处理 2，最终答案都一样，因为完全背包允许同一面额无限使用，最终是在整个集合上做极值搜索。不过从工程效率角度说，从小到大迭代跑循环比较便于调试。
3.2 凑法总数与背包问题的映射
“凑法总数”这道题（LeetCode 518）状态设计不同。我们用dp[i]表示凑成金额 i 的组合数，dp[0] = 1表示“空组合”也是一种方案，其余初始为 0。
转移方程是dp[i] += dp[i - coin]。为什么是加法？因为所有组合互斥，不同硬币组合之间是“或”的关系，总方案数等于所有子方案之和。
def change(amount, coins): dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for i in range(coin, amount + 1): dp[i] += dp[i - coin] return dp[amount]还是 coins = [1, 2, 5], amount = 5 来手算一下。初始 dp = [1, 0, 0, 0, 0, 0]。
处理 coin = 1：
| i | dp[i] 更新后 |
|---|---|
| 1 | dp[1] += dp[0] = 1 |
| 2 | dp[2] += dp[1] = 1 |
| 3 | dp[3] += dp[2] = 1 |
| 4 | dp[4] += dp[3] = 1 |
| 5 | dp[5] += dp[4] = 1 |
此时 dp 表示只用面额 1 时的组合数，全部为 1。
处理 coin = 2：
| i | dp[i] 更新后 |
|---|---|
| 2 | dp[2] += dp[0] = 2 |
| 3 | dp[3] += dp[1] = 2 |
| 4 | dp[4] += dp[2] = 3 |
| 5 | dp[5] += dp[3] = 3 |
这里 dp[2] 从 1 变成 2，因为组合 {1+1} 和 {2} 都能凑成 2；dp[5] 从 1 变成 3，因为 {1+1+1+1+1}、{1+1+1+2}、{1+2+2} 都能凑成 5。
处理 coin = 5：
| i | dp[i] 更新后 |
|---|---|
| 5 | dp[5] += dp[0] = 4 |
最终 dp[5] = 4，对应 {1+1+1+1+1}、{1+1+1+2}、{1+2+2}、{5} 四种组合。
注意：这里外层循环是硬币，内层是金额，这样统计的是组合数（不考虑顺序）。如果两层循环反过来，就会把 {1,2} 和 {2,1} 当成两种不同方案，得到排列数，在“组合”语义下是错误的。这是 518 题最容易写错的地方，没有之一。
3.3 经典变式整理与对比
| 变式 | 状态含义 | 转移关键 | 初始化 | 循环方向 |
|---|---|---|---|---|
| 最少硬币数 | dp[i]=凑成金额i的最少硬币数 | min(dp[i], dp[i-coin]+1) | dp[0]=0，其余为大数 | 正序 |
| 凑法总数 | dp[i]=凑成金额i的组合数 | dp[i] += dp[i-coin] | dp[0]=1，其余为0 | 正序 |
| 能否凑出 | dp[i]=是否能凑成i | dp[i] = dp[i] or dp[i-coin] | dp[0]=True | 正序 |
| 打印一种方案 | 额外记录choose[i] | 记录最后一次选的硬币 | 无 | 正序 |
这里再补充一个打印方案的做法。有时面试会追问“把最优组合输出出来”，这时候不能只维护 dp 数组，还要维护一个choice[i]数组，记录金额 i 第一次从哪个面额转移过来。然后从金额 amount 往回倒推，得到具体的硬币组合。
def coinChangeWithPath(coins, amount): dp = [amount + 1] * (amount + 1) choice = [-1] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): if dp[i - coin] + 1 < dp[i]: dp[i] = dp[i - coin] + 1 choice[i] = coin if dp[amount] == amount + 1: return [] path = [] while amount > 0: path.append(choice[amount]) amount -= choice[amount] return path这个技巧在“找零钱并列出具体方案”的实际业务场景里特别有用，比如自动售货机找零、收银系统里显示“应找回几张什么面额的钞票”，都能直接用上。
3.4 背包九讲视角再推导
如果熟悉背包九讲，会发现硬币凑钱就是从“完全背包”迁移过来的。标准完全背包的状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])注意这里第二项下标是i而不是i-1，因为完全背包第 i 种物品可以选多次，选了之后还能继续选。压缩到一维后就变成了：
for i in range(1, n+1): for j in range(w[i], V+1): dp[j] = max(dp[j], dp[j - w[i]] + v[i])硬币凑钱里，把 v[i] 换成 1（硬币数量），把 max 换成 min，就得到最少硬币数；把 max 换成累加，价值换成方案数，就得到凑法总数。所以背模板不是死记硬背，而是理解每部分在源问题里对应什么角色，变式题一提你就能对上号。
4. 常见问题与排查技巧实录
4.1 为什么结果一直是无穷大或显著偏大
这是最常遇到的问题，十有八九是初始化值太大导致相加溢出。比如用float('inf')初始化，然后在转移时做dp[i - coin] + 1，如果dp[i - coin]是无穷大，加 1 还是无穷大，这倒是不会出错。但有些语言里如果用Integer.MAX_VALUE又去加 1，会直接变成负数，min 比较的时候就会出鬼。
排查顺序建议这样：
- 先打印 dp 数组，看
dp[i - coin]的值是否合理； - 确认初始化标记是否足够大但没有溢出风险，推荐
amount + 1； - 确认内层循环是正序，还是写成了倒序，这个一错全错。
4.2 最少硬币数结果是 0
如果返回 0，先看dp[0]有没有被意外修改。有些人在循环里从 0 开始遍历金额，导致dp[0]被当成普通金额去转移，等于把“空状态”污染了。正确写法应该是从coin开始循环，或者单独判断i == 0跳过。
另外要注意amount = 0这种边界情况，返回 0 是合理的，因为凑 0 元不需要任何硬币。这不代表程序出错，判题时也会要求返回 0。
4.3 组合数比预期大
出现这种情况，极大概率是内外层循环写反了，把“组合数”算成了“排列数”。举个例子，coins = [1, 2]，amount = 3，组合数是 2（{1+1+1} 和 {1+2}），但如果把金额循环放外层、硬币放内层，会得到 3（多算 {2+1}）。
这个问题的本质是，组合数要求按面额“分组”统计，一旦金额放到外层，同一金额下多个面额互相转移，就会引入顺序。这也是我每次写完 518 都会特意检查的一点。
4.4 性能优化：什么时候提前退出
在求最少硬币数时，如果先对硬币按面额降序排序，有一部分情况下能找到更优解并提前截断，但 DP 本身并不依赖排序。对于常规 DP 解，时间复杂度是 O(n*amount)，空间复杂度 O(amount)，在 LeetCode 的约束下基本都能过。
如果 amount 特别大、硬币数量多，可以考虑用 BFS 求最短路。因为每个硬币相当于一次“跳转”，状态空间就是 0 到 amount 的整数点，BFS 在求最少步数问题上也天然正确，而且有些稀疏场景下比 DP 更快。不过 BFS 的空间开销更大，要结合题目数据范围选择。
4.5 实际业务中的注意点
硬币凑钱在业务里最常见的对标就是“优惠券凑单”“积分兑换凑满减”，这类场景里金额和数量可能很大，但逻辑和 LeetCode 一模一样。不同点在于业务数据往往带小数，需要先乘以 100 转成整数再算，否则浮点精度会搞得你头大。转成整数后，原来的金额上限也就跟着放大，性能上要提前评估。
另一个坑是“无解”的业务处理。技术上下返回 -1，但用户界面不能显示 -1，得提示“无法组合成功，请调整金额或面额”。所以工具函数最好封装成带状态返回，而不是只丢一个整数。
5. 变式扩展与延伸思考
5.1 每种硬币有数量限制时的处理方式
如果每种硬币的使用次数被限定，问题就从完全背包变成了多重背包。此时最直接的做法是对每种硬币做二进制拆分，把它拆成若干个 01 背包的物品，或者用单调队列优化到 O(n*amount)。面试中大部分情况不会考单调队列，二进制拆分已经够用，用一个循环遍历所有拆出来的堆即可。
5.2 最小硬币数与找零钱的贪心陷阱
有些人一看硬币面额是 1, 2, 5, 10 这种“规范面额”就下意识用贪心：优先用大面额。这个在人民币、美元这种进制下多数时候是对的，但换成 coins = [1, 3, 4], amount = 6 就翻车。贪心会先拿 4，剩 2 只能拿两个 1，共 3 枚；正确答案是 3 + 3，共 2 枚。所以只要题目没保证“贪心成立”，就必须用动态规划兜底。
5.3 完全背包与二维费用的结合
如果硬币本身有“重量”，而背包总重量也有限制，那就要开二维 dp 数组，一个维度管金额，一个维度管重量。这个其实是多重约束背包，让我想到“双 11 满减 + 运费险”这种业务，既要凑满金额，又要限制运费成本，本质上就是二维背包。
如果状态数达到 1000 x 1000，二维 DP 基本能撑住，但如果超过这个量级就要考虑滚动数组降维。写法上可以用一个二维滚动数组，每次只保留上一轮的结果，或者直接铺成一维数组然后按逆序迭代，视约束方向而定。
5.4 利用“完全背包”思维解决非背包问题
刷题刷多了会发现，很多题的“外衣”不一样，但核心都是“无限选择 + 极值/计数”。比如爬楼梯问题，如果允许一次跨任意给定步数，本质上就是求凑法的变式。再比如“零钱兑换 II”和“整数拆分”的某些变式，都逃不开这一套模型。
所以我一直建议学动态规划的人，不要孤立刷题，而是把 01 背包、完全背包、多重背包、分组背包当成一个知识树来建。建好之后，看到一个新题先在脑子里归类：是背包吗？是哪种背包？状态需要几维？转移是取 max、min 还是累加？分类完成，代码基本就是模板微调。
5.5 从硬币凑钱看动态规划通用分析框架
硬币凑钱这题虽然简单，却给我提供了一个分析所有动态规划问题的框架，我总结成四步：
- 定义状态：想清楚 dp 数组下标代表什么，值代表什么；
- 初始化：找到“零状态”，也就是递归边界，保证后续转移有起点；
- 状态转移：思考当前状态能从哪些前置状态转移而来，转移方程是什么；
- 遍历顺序：确认循环方向，是完全背包的正序，还是 01 背包的倒序，还是二维表的行优先。
任何动态规划题，面试时我都按这四步讲，考官能明显感觉到思路是清晰的。硬币凑钱就是用来练这四步的绝佳素材，因为它信息少、逻辑直接，又能引申出大量变式。
我从第一次写这道题到现在，最大的感触就是——动态规划不是玄学，它是一套可以复用的方法论。硬币凑钱正好是你把这套方法论锤进潜意识的最佳起点。把这题吃透，后面再遇到什么奇怪的“凑数”“划分”“装载”题，你都会下意识地在心里画状态表，然后稳稳地把代码写出来。
