破解硬币找零难题：动态规划原理与贪心误区-北京尧图网络

前几天给一台自助售卖机做找零算法我发现自己又兜圈子回到了“硬币找零问题”上。给定一批面额固定、数量不限的硬币比如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 模板但真到了不同场景算法选型会变输入规模与需求推荐方案原因面额数组长、金额量级在万级以内动态规划O(n*amount) 可控代码直观只需要判断能否凑出动态规划布尔数组转移只做或运算更快需要输出一组硬币DP 回溯记录数组简单且稳定硬币有库存限制多重背包改 0/1 背包完全背包模型会超用资源金额极大且硬币面额满足特殊规律可考虑贪心或数学优化但必须先验证贪心对所有金额都成立如果你只是刷完这题就换下一道记住 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 总共只有 amount1 个。每个状态扫描一次 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] 0dp[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 初始化 amount1 的原理初学 DP 时很多人好奇为什么不可达状态不用float(inf)而是用amount 1。解释如下如果某个金额 j 是可凑出的最少硬币数理论上最大是多少由于每枚硬币面额最少是1凑出 j 最多只需要 j 枚硬币因此任何可行答案一定不超过 j更不超过 amount。初始值amount 1大于任何可行答案用它来表示“还没凑出来”非常安全。用整数做哨兵的好处是避免浮点数比较带来的误差也让打印 DP 数组时看起来干净。判断无解时只需检查dp[amount]是否还等于初始化哨兵值if dp[amount] amount 1: return -1如果amount 0dp[0] 0不会等于哨兵直接返回0这个特例不需要额外写 if很省心。3.4 复杂度与空间取舍自底向上的 DP 时间复杂度和记忆化搜索一样也是 O(n * amount)空间复杂度从递归状态的函数栈变成了数组是稳定 O(amount)一维版本。在一般的目标金额范围内这个表现非常理想。实际工程上如果 amount 是十万级硬币种类几十个总操作大约百万次到千万次现代机器毫无压力。但如果 amount 上了千万或者面额分布极稀疏直接用数组可能不划算。另一种思路是用字典只记录可达金额节点这样空间随可达状态数增长而不是总金额。不过这种写法往往带来查找开销和更复杂的回溯我通常只在金额范围特别大但目标值数量不多时采用。4. 进阶追问最少数量之外还要输出具体的找零方案4.1 用 last 数组记录每一步选择有时产品需求不只是“告诉我需要几枚硬币”而是“打印出到底是哪些硬币”。比如自动售卖机需要找零硬件要按金币种类吐币只知道数量没有用。我们可以在 DP 数组之外额外维护一个数组lastlast[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(reverseTrue) 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元一共需要 411共3枚硬币。但最优解明显是 33只需要2枚。贪心在这里给出的答案比正确答案多1。再来一个更反直觉的例子面额[1, 5, 6, 9, 10]目标金额18。贪心先选10剩下8再选6剩下2用两张1总枚数 10611 4枚。实际上用两张9元也就是 99 18只需要2枚。这类反例说明一个核心问题贪心是局部最优一旦选了某个较大面额可能把后面更优的组合空间堵死了。5.3 怎么判断一组硬币面额能否使用贪心有一些数学研究把“贪心算法对该硬币系统总是正确的”称为规范硬币系统但实际工程里很少需要做这么重的理论验证。我在项目中的办法很简单当硬币集合是固定的用动态规划做基准在常见金额范围内批量测试贪心结果和 DP 结果。如果一致说明在这个测试范围内用贪心没问题如果出现不一致绝对不能用贪心。比较两种方法的价值维度贪心动态规划时间复杂度基本是 O(n) 或 O(1)O(n * amount)代码复杂度很低略高对任意币制是否最优不一定一定是否能处理库存限制几乎不能保证可以扩展是否输出方案容易但方案不一定最优配合 last 数组输出最优我在真实业务里仍然偏向 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 组合数与最少数量的一行差别有些业务场景问的不是最少用多少枚而是“有多少种凑法”比如优惠券组合、代币兑换方案数量。这个问题也有一个很容易记错方向的 dpdef 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 高频错误的写法和修法写这题几年下来我总结了一张自己常看的排查表。如果你跑测试的结果不对先对着表逐条核对错误现象根本原因修正方法硬币种类多结果比预期偏大内层循环倒序了硬币变成最多用一次完全背包内层正序遍历某几个金额返回-1但人工组合能凑出来初始化哨兵不统一dp[0] 没设0保证 dp[0]0使用递归加 lru_cache 后仍超时递归中有-1参与min比较不可达状态用float(inf)金额为1时返回-1忘了设置哨兵amount1为初始值不可达状态不会只因为金额小而自动标记输出方案时出现死循环last 数组没有记录有效迁移或记录面额是-1更新 dp 时才更新 last组合数答案是排列数外层金额循环、内层硬币循环改成外层硬币、内层金额第一行是最常见也最隐蔽的坑。尤其当你背了模板却没理解完全背包和 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第一条是常规测试225 或 551 都是3枚。第二条验证最小面额不是1时会拉出不可达状态。第三条验证空金额返回0。第四条是上一节里贪心失效的反例专门防御有人把贪心逻辑夹带进来。第五条验证金额小于所有面额时的表现。第六条中5可以拆成23或221但最优其实是 23正好2枚进一步检验转移时是否忽略可行解。7.3 调试心得打印 DP 数组比打断点更管用如果你已经写过代码但结果不对我的建议是先不要硬看逻辑把dp数组打出来从第0个元素开始看一眼。打印出一段只有十几个数字的数组往往几秒钟就能发现状态转移的中断点。举个例子调试硬币[1, 3, 4]、目标金额6 时正确的一维 DP 数组应该长这样0到6dp[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内层应该正循环还是倒循环。这套思维一旦成了习惯再去处理变体会轻松得多。

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

相关推荐

HelloAGENTS中standby与global部署模式选型指南

C# Winform酒店管理系统源码：从数据库配置到房态与退房结账

Windows鼠标指针一键切换方案：原理、工具与自定义实践

更多资讯

面向红外小目标检测的方向感知偏移增强与动态可变形卷积

读时建模 vs 写时建模：问数平台如何对接多源异构业务系统

智慧农业数据采集从零到一：MQTT 接入边缘网关完整教程（附实测可运行代码）

RocketMQ 集群特性

基于微信小程序的ACG手办商店系统（毕设源码+文档）

Java在AI时代不会消亡：停更事件背后的真实技术演进与选型策略

今日更新

Verilog实现FPGA密码锁：矩阵键盘与状态机设计实战

数据服务监控运维实战：从指标体系到告警治理与故障排查

FreeRTOS任务通知实战详解：内核原理、API与避坑指南

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？