破解硬币找零难题：动态规划原理与贪心误区

前几天给一台自助售卖机做找零算法，我发现自己又兜圈子回到了“硬币找零问题”上。给定一批面额固定、数量不限的硬币，比如1元、2元、5元，目标金额是11元，问最少用几枚硬币能凑出来；如果怎么都凑不出来，返回-1。这题看起来简单到像是“先拿大面额去怼，剩下的找零钱补一补”，然而真把代码写完，丢到一些刁钻用例里，就会看到一堆问题：有的金额凑不出来，有的用贪心会给出错误答案，有的甚至优化方向都搞反了。“硬币找零、最少硬币数”是学习动态规划绕不过去的入门题，也是很多支付类、游戏代币兑换类系统的实际需求，值得把它的原理聊透。

这篇文章我打算用完整的思路做一次复盘，从状态设计讲到递归和记忆化搜索，再讲自底向上的动态规划，最后扩展到输出找零方案、贪心算法什么时候可用、硬币库存有限这类常见变体。准备算法面试的人可以把它当复习材料，正在做实际业务系统、需要处理余额找零或代币分摊的人，也能从里面找到可以落到代码里的思路。

1. 问题定义与状态设计：这道题难在你以为它没有难点

1.1 先看清题目的隐含条件

原题表面很简洁：输入一个硬币面额数组coins，比如[1, 2, 5]，再输入总金额amount = 11，求最少硬币数量。硬币“每种无限量供应”是常见版本，这意味着你可以在组合里多次使用同一个面额。另一个常见的坑是“最小面额不一定是1”，所以有些金额天然不可达，比如硬币只有[2]，总金额是3，无论怎么凑都凑不出来，这时候要返回-1，而不是返回一个错误的0或者继续死循环。

边界条件也没有想象中简单：目标金额为0时，答案是0，因为不需要任何硬币。这个点看起来废话，但很多人在初始化 DP 数组时把dp[0]设置错了，导致整个状态转移链崩掉。

有时候还会遇到一种更隐蔽的描述：它不是问“最少用多少枚硬币”，而是问“有多少种组合方式”。这两种问法虽然都叫找零问题，但转移逻辑和去重方式差别非常大，下文会单独比较。先记住最基本的目标：求最少数量，不是求方案数，也不是求字典序最小的一组解。

1.2 状态设计前必须想明白的四件事

动态规划最核心的环节不是写循环，而是把“状态是什么”说清楚。我的习惯是动手前先问四个问题。

第一，状态表示谁的什么信息。对硬币找零来说，最常见的定义是dp[i]表示“凑出金额 i 需要的最少硬币数”。下标是钱的金额，而不是面额的索引。这么设计的好处是目标金额连续，填表方便；坏处是当目标金额很大时，空间会随着金额线性增长。

第二，子问题怎么切分。从大金额往小看，如果你当前是在凑金额 i，那么随便选择一枚硬币 c，只要c <= i，就相当于先用掉这枚硬币，接着去凑i - c。子问题的规模变小了，而且原问题的最优解一定包含某个子问题的最优解，这就是最优子结构。

第三，边界值是什么。边界必须是“已经凑完0元”的状态，所以dp[0] = 0。其它未计算的金额要设置成一个足够大的“不可达”标记，比如amount + 1。这个标记为什么不是随便一个大数？因为如果问题有解，每枚硬币面额至少是1，那么最优解最多用 amount 枚硬币，再多没有任何意义，所以amount + 1天然比任何可行解都大。

第四，硬币能不能重复使用。这个问题直接决定循环的遍历方向。无限量硬币是典型完全背包，内层金额要正序遍历；如果硬币数量有限，那就是多重背包，内层要从大到小枚举，否则会把同一枚硬币重复使用多次。这个方向问题我会在第三章结合代码细讲，这里先把结论记住。

把上面四个问题想清楚，写出来的代码基本不会跑偏。反过来，如果状态定义模模糊糊就套模板，十个里有九个最后不知道自己在 Debug 什么。

1.3 选哪种算法不只看金额，还要看后续需求

很多同学学这题只记住了一个一维 DP 模板，但真到了不同场景，算法选型会变：

如果你只是刷完这题就换下一道，记住 DP 模板就行。但如果你在业务系统里碰到类似问题，我会劝你多想一层：是否要打印清单，库存是否有限，硬币面额是否会动态变化，目标金额的上限是多少。这些额外需求会在算法选型时起到关键作用。

2. 自顶向下先跑通：递归加缓存，最简单也最容易移植

2.1 暴力递归是这个问题的最诚实表达

我最怕一上来就给别人甩 DP 模板，因为一旦模板里某个条件写错，初学者完全不知道如何排查。递归版本虽然性能差，但它和人脑的思维方式最接近，而且非常好调试。

用函数dfs(rem)表示“凑出剩余金额 rem 所需的最少硬币数”。如果 rem 恰好是0，说明已经凑完，返回0。否则遍历所有面额 c，只要c <= rem，就递归去凑rem - c，最后在所有方案里取最小值。核心写法如下：

def coin_change_recursive(coins, amount): def dfs(rem): if rem == 0: return 0 best = float("inf") for c in coins: if rem >= c: best = min(best, dfs(rem - c) + 1) return best ans = dfs(amount) return -1 if ans == float("inf") else ans

这个代码虽然能算，但一旦 amount 到几十，运行时间就会指数爆炸。原因很直白：dfs(10)会递归调用dfs(8)、dfs(9)、dfs(5)等，而dfs(9)继续往下调用，很多子状态被反复计算，完全没有复用。

2.2 记忆化搜索是如何消除重复的

递归慢不是因为思路错，是因为重复计算太多。拿硬币[1, 2, 5]、金额11举例，不同递归路径会在大量相同的剩余金额上反复展开，比如dfs(6)被dfs(7)、dfs(8)、dfs(11)从不同路径碰到无数遍。

解决办法非常简单：准备一个缓存字典或数组，第一次算出某个 rem 的结果就存起来，后面再遇到同一个 rem 直接读缓存。Python 里最方便的是用functools.lru_cache，代码几乎不用改结构：

from functools import lru_cache def coin_change_memo(coins, amount): @lru_cache(None) def dfs(rem): if rem == 0: return 0 best = float("inf") for c in coins: if rem >= c: best = min(best, dfs(rem - c) + 1) return best ans = dfs(amount) return -1 if ans == float("inf") else ans

加上这行装饰器，状态rem从 0 到 amount 总共只有 amount+1 个。每个状态扫描一次 coins，所以时间复杂度是 O(amount * n)，空间复杂度是 O(amount)。这个版本在很多场景下可以直接跑，实际上它就是自顶向下形式的动态规划，递归只是用栈去模拟状态的访问顺序。

2.3 递归版本里要注意的三个细节

递归版本看起来短，但有三个坑我踩过，提醒一条条列出来。

第一个坑是递归深度。目标金额如果达到 2000，硬币面额全是1，递归会深入2000层。Python 默认递归深度约1000，直接报 RecursionError。可以在模块开头设置sys.setrecursionlimit(10000)，但递归深度太深终究不是稳定方案。如果面试官把 amount 设成10万，建议直接讲自底向上 DP。

第二个坑是返回值处理。dfs里用float("inf")表示凑不出来，外面再判断一次并转成 -1，这比较清晰。但有人会习惯性地把不可达写成 -1，然后在min里参与比较，这就坏了，因为 -1 永远比正数小，算法会错误地认为“不可达”是最优解。

第三个坑是关于排序的误解。有人会把硬币降序排列，然后试图在 DFS 里找到第一条能走通的路径就返回，这种思路其实变成了贪心算法，只在特定币制下才成立。后面我会专门说这是什么条件，但现在记住：排序可以做剪枝，但不能代替全状态搜索。

3. 自底向上写动态规划：两层循环的顺序藏着完全背包的玄机

3.1 二维 DP 的含义与转移方程

自顶向下递归其实是“用多少，先挖下去”，自底向上的 DP 则是“从0元开始，一步一步往上填”。先介绍二维写法，因为它把逻辑展示得更完整，适合理解初始化和转移过程。

假设硬币种类是 n，面额数组记为coins[0..n-1]。定义dp[i][j]表示用前 i 种硬币（即coins[0]到coins[i-1]）凑出金额 j 需要的最少硬币数量。初始化时，dp[0][0] = 0，dp[0][j]（j 大于0）全部设成amount + 1，因为不用任何硬币时，只有0元可以凑出来。

状态转移有两种来源。第一种是不使用第 i 种硬币，那么dp[i][j] = dp[i-1][j]。第二种是使用第 i 种硬币至少一次。这里尤其要注意：因为硬币无限量使用，使用一次之后，仍然可以继续使用这种硬币，所以子状态是dp[i][j - coins[i-1]]，而不是dp[i-1][j - coins[i-1]]。转移方程写出来是：

dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i-1]] + 1)

这个方程和 0/1 背包最大的区别就在第二个来源使用的是“当前行”，而不是“上一行”。如果写成dp[i-1][j - coins[i-1]]，就变成每种硬币最多只能用一次了，那明显不符合题意。

3.2 一维 DP 和完全背包的遍历方向

二维 DP 很好懂，但实际工程项目基本都是用滚动数组降维，也就变成了最常见的一维写法：

def coin_change_dp(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for c in coins: # 外层遍历硬币面额 for i in range(c, amount + 1): # 内层遍历金额，必须正序 dp[i] = min(dp[i], dp[i - c] + 1) return -1 if dp[amount] == amount + 1 else dp[amount]

为什么内层要正序遍历？这里要用完全背包的概念解释。内层循环一步步从左到右更新，当你在位置 i 计算dp[i]时，dp[i - c]可能已经在同一轮内被当前这枚硬币 c 更新过了，这相当于 dp 数组允许你在同一个面额 c 上反复叠加，因此硬币可以无限次使用。

你可以反向再体会一下：如果内层循环改成从 amount 往前到 c 的倒序遍历，每次更新dp[i]时用到的dp[i - c]还是上一轮没有掺入当前硬币的旧值，结果就是每枚硬币最多只用一次，变成 0/1 背包。很多刷动态规划题的人在这道题上出错，不是方程记错了，而是内层方向搞反了，最后结果可能比真实答案大。

还有一种写法是外层金额、内层硬币：

for i in range(1, amount + 1): for c in coins: if i >= c: dp[i] = min(dp[i], dp[i - c] + 1)

这种写法在“最少数量”场景下也正确，因为它不区分硬币使用的先后顺序，本质上仍然是在枚举最后一次使用的面额。但如果题目改成“组合计数”，这个写法会带来顺序重复问题，把不同顺序的组合也当成不同方案，后面变体部分我会再次提到。为了通用，建议优先记住外层硬币、内层金额正序的完全背包写法。

3.3 初始化 amount+1 的原理

初学 DP 时，很多人好奇为什么不可达状态不用float("inf")，而是用amount + 1。解释如下：如果某个金额 j 是可凑出的，最少硬币数理论上最大是多少？由于每枚硬币面额最少是1，凑出 j 最多只需要 j 枚硬币，因此任何可行答案一定不超过 j，更不超过 amount。初始值amount + 1大于任何可行答案，用它来表示“还没凑出来”非常安全。

用整数做哨兵的好处是避免浮点数比较带来的误差，也让打印 DP 数组时看起来干净。判断无解时只需检查dp[amount]是否还等于初始化哨兵值：

if dp[amount] == amount + 1: return -1

如果amount = 0，dp[0] = 0，不会等于哨兵，直接返回0；这个特例不需要额外写 if，很省心。

3.4 复杂度与空间取舍

自底向上的 DP 时间复杂度和记忆化搜索一样，也是 O(n * amount)，空间复杂度从递归状态的函数栈变成了数组，是稳定 O(amount)（一维版本）。在一般的目标金额范围内，这个表现非常理想。实际工程上，如果 amount 是十万级，硬币种类几十个，总操作大约百万次到千万次，现代机器毫无压力。

但如果 amount 上了千万或者面额分布极稀疏，直接用数组可能不划算。另一种思路是用字典只记录可达金额节点，这样空间随可达状态数增长，而不是总金额。不过这种写法往往带来查找开销和更复杂的回溯，我通常只在金额范围特别大但目标值数量不多时采用。

4. 进阶追问：最少数量之外还要输出具体的找零方案

4.1 用 last 数组记录每一步选择

有时产品需求不只是“告诉我需要几枚硬币”，而是“打印出到底是哪些硬币”。比如自动售卖机需要找零，硬件要按金币种类吐币，只知道数量没有用。我们可以在 DP 数组之外额外维护一个数组last，last[i]记录“凑出金额 i 时所使用的最后一枚硬币面额”。

在一维 DP 更新时，一旦发现使用当前面额 c 可以得到更优解，就把last[i]设为 c。最后从amount开始沿着last一路回溯，跳转到i - last[i]，直到金额变成0，收集到的面额就是一组可行解。实现如下：

def coin_change_with_path(coins, amount): dp = [amount + 1] * (amount + 1) last = [-1] * (amount + 1) dp[0] = 0 for c in coins: for i in range(c, amount + 1): if dp[i - c] + 1 < dp[i]: dp[i] = dp[i - c] + 1 last[i] = c if dp[amount] == amount + 1: return None path = [] i = amount while i > 0: c = last[i] path.append(c) i -= c return path

需要注意，如果硬币面额本身就是多枚相同金额的库存，用last记录面额可能不够区分“用的是哪一枚”。比如面额数组是[1, 1, 5]，两个1元硬币是不同的物理实体，但它们作为代币价值等价，所以在最少数量问题上记录面额已经够用。如果必须区分库存编号，就需要在状态里记录硬币索引，这通常会和库存约束一起出现，第六章会简单展开。

4.2 如果要求输出全部可行组合怎么办

输出一组解用 DP 速度快，输出全部可行组合又是另一回事。如果组合数量极大，复杂度必然指数级，DP 本身不适合直接枚举全量。常见做法是排序后做 DFS 剪枝，按面额从大到小枚举，并保证枚举顺序单调，避免[2, 3]和[3, 2]被当作两种组合：

def print_all_ways(coins, target): coins.sort(reverse=True) res = [] current = [] def dfs(start, remaining): if remaining == 0: res.append(current[:]) return for idx in range(start, len(coins)): c = coins[idx] if c > remaining: continue current.append(c) dfs(idx, remaining - c) # 同一面额还能再用，所以下一轮仍从 idx 开始 current.pop() dfs(0, target) return res

这种写法在剩余金额很小但面额很多时剪枝效果不好。可以额外加一个剪枝：如果当前剩余金额小于所有剩余硬币面额的最小值，说明不可能凑完，提前返回。不过实际开发中如果只是要“任意一组最少解”，我强烈建议用last回溯，不要用 DFS 枚举，否则解一多就跑飞了。

5. 贪心算法的诱惑与雷区

5.1 为什么现实货币下贪心基本是对的

每次讲到硬币找零，都会有人提出“为什么不用贪心”的疑问：直接把金额从大到小用大面额硬凑，不是又快又直观吗。这里必须区分“数学上永远正确的贪心”和“特定币制下行为正确的贪心”。

以现实生活中常见货币为例，人民币纸币面额是1、5、10、20、50、100，美分硬币是1、5、10、25。这些币制有一个隐含特征：大面额往往能被若干个小面额拼成，且进制规则让每一步选择最大可用面额都不会影响后续组合。你找99元，先拿50元，剩下的49用20、20、5、2、2，结果确实是最少硬币。因为现实币制设计时考虑了找零方便，保证“尽量用大额”就是最优。

但从算法角度，这种“现实经验”不值得无条件推广。你一旦把币制换成任意输入，贪心就崩了。

5.2 面额组合反例：贪心不是通用解法

经典反例是硬币面额[1, 3, 4]，目标金额 6。按贪心思路，先选最大面额4，剩余2，只能用两张1元，一共需要 4+1+1，共3枚硬币。但最优解明显是 3+3，只需要2枚。贪心在这里给出的答案比正确答案多1。

再来一个更反直觉的例子：面额[1, 5, 6, 9, 10]，目标金额18。贪心先选10，剩下8，再选6，剩下2用两张1，总枚数 10+6+1+1 = 4枚。实际上用两张9元，也就是 9+9 = 18，只需要2枚。这类反例说明一个核心问题：贪心是局部最优，一旦选了某个较大面额，可能把后面更优的组合空间堵死了。

5.3 怎么判断一组硬币面额能否使用贪心

有一些数学研究把“贪心算法对该硬币系统总是正确的”称为规范硬币系统，但实际工程里很少需要做这么重的理论验证。我在项目中的办法很简单：当硬币集合是固定的，用动态规划做基准，在常见金额范围内批量测试贪心结果和 DP 结果。如果一致，说明在这个测试范围内用贪心没问题；如果出现不一致，绝对不能用贪心。

比较两种方法的价值：

我在真实业务里仍然偏向 DP，因为金额上限通常可控，硬币面额又是动态配置的，如果为了省一点时间引入贪心，等某天运营在后台把面额改成[1, 3, 4]，线上就会出现所有找零多吐一块钱的情况，那比多算几轮循环的代价高多了。

6. 扩展变体：库存有限、组合数、实际找零中的约束

6.1 硬币库存有限：多重背包的改造方式

业务系统和单纯算法题最大的区别是硬币不再“无限量供应”。自动售货机里的1元找零可能只有30枚，5元找零只有10枚。此时硬币面额使用次数有上限，问题变成多重背包。

直接做法是在一维 DP 上多套一层枚举使用次数 k。伪代码思路：

for c in coins: for i in range(amount, -1, -1): # 关键是倒序 for k in range(1, min(count_of_c, i // c) + 1): dp[i] = min(dp[i], dp[i - k * c] + k)

为什么这里要倒序？因为每枚硬币的数量有限制，如果像完全背包那样正序遍历，同一枚硬币可能被重复计入超过它的库存数量。倒序能保证当前硬币带来的更新不会被本轮后续再次使用，这才是正确逼近“物品最多一次”的关键。

如果库存数量很大，比如某面额有5000枚，三层循环会慢。优化手段是二进制拆分：把 5000 拆成1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 剩余900等若干份，每份看作一个独立物品，然后转成普通 0/1 背包。这样物品数量从5000降到约13个，效率提升明显。

6.2 组合数与最少数量的一行差别

有些业务场景问的不是最少用多少枚，而是“有多少种凑法”，比如优惠券组合、代币兑换方案数量。这个问题也有一个很容易记错方向的 dp：

def ways_to_change(coins, amount): dp = [0] * (amount + 1) dp[0] = 1 for c in coins: for i in range(c, amount + 1): dp[i] += dp[i - c] return dp[amount]

这里dp[i]表示凑出金额 i 的组合数，初始化dp[0]=1表示“空组合”也是一种方式。外层遍历硬币面额，内层正序，这样能保证每种面额使用的次数不限，并且不会把[2,3]和[3,2]重复计数，因为内层循环只允许在已经处理过前几种面额的基础上继续叠加。

如果写的顺序不对，把硬币循环放内层，就会变成求排列数，某些场景下数量会暴涨。面试中如果遇到的是“最少硬币数量”，这节内容可不深究；但做成长方案交付时，区分组合与排列非常关键。

6.3 实际项目中被忽略的找零约束

除了库存限制，真实系统还有“可能不存在最小面额1元”的尴尬情况。假设某套代币面额是2、3、5，那么金额1就无法表示。此时如果支付系统硬要找零，就会出现用户账户永远差1单位的问题。线上处理通常有两种方案：要么在结算前做余额校验，凑不出就提示换一种支付方式；要么在余额计算中配置“抹零规则”，允许剩余不足最小面额的零头四舍五入或转成优惠券。

另外一个约束是硬币面额可能不是固定数组，而是运营动态维护的。这种情况下不建议把币制写死在代码里，更不要拍脑袋选择贪心，应该直接交给 DP 统一处理。动态规划虽然每次都要重新计算，但功能正确性比微小的性能消耗更值得优先保证。

7. 常见错误和调试经验：这些问题我每次写都会踩

7.1 高频错误的写法和修法

写这题几年下来，我总结了一张自己常看的排查表。如果你跑测试的结果不对，先对着表逐条核对：

第一行是最常见也最隐蔽的坑。尤其当你背了模板却没理解完全背包和 0/1 背包区别时，可能换一题就把循环顺序写串了。

7.2 一套可以反复使用的测试用例

调试阶段我建议准备这样一组断言，覆盖大部分边界：

assert coin_change_dp([1, 2, 5], 11) == 3 assert coin_change_dp([2], 3) == -1 assert coin_change_dp([1], 0) == 0 assert coin_change_dp([1, 3, 4], 6) == 2 assert coin_change_dp([2, 5, 10], 1) == -1 assert coin_change_dp([1, 2, 3], 5) == 2

第一条是常规测试，2+2+5 或 5+5+1 都是3枚。第二条验证最小面额不是1时会拉出不可达状态。第三条验证空金额返回0。第四条是上一节里贪心失效的反例，专门防御有人把贪心逻辑夹带进来。第五条验证金额小于所有面额时的表现。第六条中，5可以拆成2+3或2+2+1，但最优其实是 2+3，正好2枚，进一步检验转移时是否忽略可行解。

7.3 调试心得：打印 DP 数组比打断点更管用

如果你已经写过代码但结果不对，我的建议是先不要硬看逻辑，把dp数组打出来，从第0个元素开始看一眼。打印出一段只有十几个数字的数组，往往几秒钟就能发现状态转移的中断点。

举个例子，调试硬币[1, 3, 4]、目标金额6 时，正确的一维 DP 数组应该长这样（0到6）：

dp[0]=0 dp[1]=1 dp[2]=2 dp[3]=1 dp[4]=1 dp[5]=2 dp[6]=2

如果你跑完发现dp[3]=2，那大概率是初始化时某些特殊路径没走到，或者循环方向写错了。每次修改算法后，用极小的金额多打印几条状态递推链路，基本能把任何状态转移错误揪出来。

最后再分享一个我在项目里的心得。硬币找零问题的 DP 模板其实很短，但真正让我觉得难的往往不是代码本身，而是状态定义和边界条件。我每到一个新场景，都会先强迫自己用中文说清楚：dp[i]到底表示什么，初始化为什么是0，内层应该正循环还是倒循环。这套思维一旦成了习惯，再去处理变体会轻松得多。