1. 从找零钱这个场景说起为什么它成了动态规划的经典入口找零钱这个问题几乎每个学动态规划的人都会碰到。题目本身不复杂给定几种不同面额的硬币再给定一个目标金额问凑出这个金额最少需要几枚硬币或者一共有多少种凑法。听起来像是小学奥数题但它背后藏着动态规划最核心的思维方式——把大问题拆成小问题用小问题的答案推导大问题的答案。我第一次接触这个题的时候第一反应是贪心每次尽量用面额最大的硬币不就行了比如面额是1、5、10、25目标金额是63那先用两个25剩下13再用一个10剩下3最后三个1总共6枚。这个答案对不对在这个面额组合下确实是对的。但如果面额换成1、3、4目标金额是6呢贪心会先拿4剩下2再拿两个1总共3枚。但最优解是33只要2枚。贪心在这里就翻车了。这就是找零钱问题最有价值的地方它用一个极其简单的场景让你直观地看到贪心和动态规划的分界线在哪里。贪心只考虑眼前最优动态规划则考虑全局最优。很多人在学习dp的时候觉得状态转移方程像是从天上掉下来的其实不是它就是从这种当前选择会影响后续选择的困境中推导出来的。这篇文章我会围绕背包问题这个大框架下的找零钱变体把dp训练的完整思路拆开来讲。不管你是刚接触动态规划的新手还是刷了一些题但总觉得没抓到本质的进阶者我都会从状态定义、转移方程推导、空间优化、边界处理、常见变体这几个维度把这个问题讲透。文章里会有大量我实际写代码时踩过的坑和总结的技巧不是那种照着教科书念的八股文。2. 找零钱问题的两种面孔最少硬币数与凑法计数2.1 最少硬币数优化问题的典型代表最少硬币数的问题是给定硬币面额数组coins和目标金额amount求凑出该金额所需的最少硬币数量。如果无法凑出返回-1。这个问题的核心在于每一个金额的最优解都可以由比它小的某个金额的最优解加上一枚硬币得到。比如我想知道凑出金额11最少需要几枚硬币我可以看金额10的最优解加一枚面额1的硬币或者金额6的最优解加一枚面额5的硬币或者金额1的最优解加一枚面额10的硬币。在所有可能的上一个金额中取最小值就是金额11的答案。用数学语言表达就是dp[i] min(dp[i - coin] 1) for each coin i其中dp[i]表示凑出金额i所需的最少硬币数。dp[0] 0因为凑出金额0不需要任何硬币。对于无法凑出的金额dp[i]保持为一个哨兵值通常用amount 1或者float(inf)。我刚开始写这个题的时候犯过一个很典型的错误把dp数组初始化为0然后直接跑转移方程。结果所有dp[i]都变成了0因为min(0, ...)永远是0。这个错误的本质是没有区分无法凑出和凑出需要0枚硬币这两种状态。金额0确实需要0枚硬币但金额3在只有面额2的硬币时是无法凑出的这两者必须用不同的值来表示。正确的初始化方式是dp[0] 0其余所有dp[i]初始化为一个不可能达到的大值。这个大值的选择也有讲究用amount 1就够了因为即使全用面额1的硬币最多也只需要amount枚。用float(inf)也可以但在某些语言里要注意整数溢出的问题。2.2 凑法计数组合问题的另一种思路凑法计数的问题是给定硬币面额数组和目标金额求凑出该金额的组合数不区分顺序。比如面额是1、2、5目标金额是5那么组合有5、221、2111、11111共4种。注意这里说的是组合而不是排列。122和212算同一种组合因为它们用的硬币面额和数量完全一样只是顺序不同。这一点非常关键因为它直接决定了遍历的顺序。凑法计数的转移方程看起来和最少硬币数很像dp[i] dp[i - coin] for each coin i但这里有一个极其容易踩的坑外层循环遍历硬币内层循环遍历金额得到的是组合数如果反过来外层遍历金额内层遍历硬币得到的是排列数。这个区别我在下面会用具体例子详细展开。2.3 两种问题的对比与联系维度最少硬币数凑法计数目标最小化硬币数量统计所有组合转移方式取min累加求和初始化dp[0]0其余为无穷大dp[0]1其余为0遍历顺序硬币和金额的顺序不影响结果外层硬币内层金额得组合数无法凑出时返回-1返回0典型变体完全背包求最小值完全背包求方案数这两个问题都属于完全背包的范畴因为每种硬币可以使用无限次。如果是每种硬币只能用一次那就变成了0-1背包的问题转移方程需要倒序遍历金额。这个细节在后面会专门讲。3. 状态转移方程是怎么推出来的而不是背出来的3.1 从递归到递推自顶向下的思考方式很多人学dp的方式是直接背转移方程但这样遇到变体就懵了。我的建议是先用递归的方式把问题想清楚再改写成递推。以最少硬币数为例用自顶向下的思路我想求凑出金额n的最少硬币数我可以枚举最后一枚硬币用的是什么面额。如果最后一枚用的是面额c那么剩下的金额是n - c问题就变成了求凑出n - c的最少硬币数。在所有可能的c中取最小值再加上最后一枚硬币就是答案。写成递归函数def coin_change(coins, amount): if amount 0: return 0 if amount 0: return float(inf) res float(inf) for coin in coins: sub coin_change(coins, amount - coin) if sub ! float(inf): res min(res, sub 1) return res这个递归的问题在于大量重复计算。比如算金额10的时候会算金额5算金额9的时候也会算金额5金额5被反复计算了多次。加一个备忘录memo就能解决def coin_change(coins, amount, memo{}): if amount 0: return 0 if amount 0: return float(inf) if amount in memo: return memo[amount] res float(inf) for coin in coins: sub coin_change(coins, amount - coin, memo) if sub ! float(inf): res min(res, sub 1) memo[amount] res return res这就是自顶向下的动态规划也叫记忆化搜索。它的好处是思路直观直接从问题的定义出发不需要考虑遍历顺序。缺点是递归深度可能很大而且有函数调用的开销。3.2 自底向上的改写从最小子问题开始填表把上面的递归改成自底向上的递推就是标准的dp写法def coin_change(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这里的遍历顺序是外层遍历金额内层遍历硬币。对于最少硬币数这个问题内外层谁在外面其实都可以因为dp[i]只依赖于比i小的金额而不管硬币的遍历顺序如何dp[i - coin]都已经计算过了。但如果是凑法计数遍历顺序就至关重要了。这一点我在下一节会详细展开。3.3 为什么dp[0]的初始化如此关键dp[0]的初始化看起来是个小细节但它决定了整个dp数组的语义是否正确。对于最少硬币数dp[0] 0表示凑出金额0需要0枚硬币这是符合直觉的。其余位置初始化为无穷大表示暂时还不知道能不能凑出。对于凑法计数dp[0] 1表示凑出金额0有1种方法就是什么都不选。这个初始化乍看有点反直觉但它是正确的。因为当你用一枚面额恰好等于目标金额的硬币时dp[amount] dp[0]如果dp[0]是0这个方案就不会被计入。所以dp[0] 1是凑法计数能正确工作的前提。我见过不少人在凑法计数里把dp[0]初始化成0然后发现所有结果都是0排查半天才发现是初始化的问题。这种坑踩过一次就记住了。4. 遍历顺序的玄机组合数与排列数的分水岭4.1 外层硬币内层金额为什么得到的是组合数先看代码def count_combinations(coins, amount): 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]这段代码的逻辑是逐个考虑每种硬币对于每种硬币决定它在凑出各个金额时用几枚。以面额[1, 2, 5]、目标金额5为例手动模拟一下处理硬币1dp[1]1, dp[2]1, dp[3]1, dp[4]1, dp[5]1只用面额1每个金额只有1种凑法处理硬币2dp[2]dp[0]1变成2, dp[3]dp[1]1变成2, dp[4]dp[2]2变成3, dp[5]dp[3]2变成3处理硬币5dp[5]dp[0]1变成4最终dp[5]4对应四种组合11111、1112、122、5。关键在于每种硬币只被引入一次。当处理硬币2的时候所有包含硬币2的组合都是在之前只含硬币1的基础上加上若干个2得到的。硬币2不会出现在硬币1之前被考虑所以不会产生2111和1211这种重复计数。4.2 外层金额内层硬币排列数是怎么冒出来的再看另一段代码def count_permutations(coins, amount): dp [0] * (amount 1) dp[0] 1 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] dp[i - coin] return dp[amount]这段代码的逻辑是对于每个金额枚举最后一枚硬币用的是什么面额。同样以面额[1, 2, 5]、目标金额5为例dp[1] dp[0] 1只有1dp[2] dp[1] dp[0] 1 1 211 和 2dp[3] dp[2] dp[1] 2 1 3111、12、21dp[4] dp[3] dp[2] 3 2 51111、112、121、211、22dp[5] dp[4] dp[3] dp[0] 5 3 1 99种排列中包含了122、212、221这三种它们在组合计数中只算一种但在排列计数中算了三种。4.3 一个记忆技巧和一个验证方法记忆技巧很简单外层循环是决策的维度内层循环是状态的维度。当外层是硬币时你是在逐个做要不要用这种硬币的决策每种硬币的决策只做一次所以是组合。当外层是金额时你是在每个金额上做最后一枚用什么的决策同一个金额可能被不同的硬币多次到达所以是排列。验证方法也很直接拿一个简单的例子手动跑一遍看看结果是否符合预期。比如面额[1, 2]、目标金额3组合数应该是2111、12排列数应该是3111、12、21。跑一下代码就能验证你的遍历顺序对不对。注意在面试中如果遇到凑法计数的题目一定要先确认是组合还是排列。这两种理解的答案完全不同而且面试官很可能就是通过这个来考察你对遍历顺序的理解。5. 空间优化与边界处理那些教科书不会告诉你的细节5.1 一维数组已经是最优了吗找零钱问题的dp数组大小是amount 1这已经是最优的空间复杂度了。因为dp[i]只依赖于dp[i - coin]而这些值都在同一个数组中所以一维数组就够了。但有些变体问题可能需要二维数组。比如如果每种硬币有数量限制多重背包就需要额外的维度来记录每种硬币用了多少。再比如如果问题变成了用恰好k枚硬币凑出金额n那就需要二维dpdp[k][n]。对于标准的完全背包找零钱问题一维数组是标准解法不需要考虑进一步的空间优化。5.2 整数溢出的隐患与防范在最少硬币数问题中如果用float(inf)作为初始值在Python里没问题但在C或Java里就要小心了。float(inf) 1还是float(inf)但如果是用INT_MAX作为哨兵值INT_MAX 1就会溢出成负数导致min操作得到错误的结果。防范方法有两种一是用amount 1作为哨兵值因为最多只需要amount枚硬币amount 1一定大于任何合法解二是在做加法之前先判断当前值是否为哨兵值如果是就跳过。# 方法一用amount1作为哨兵 dp [amount 1] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] amount else -1 # 方法二加法前判断 dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i and dp[i - coin] ! float(inf): dp[i] min(dp[i], dp[i - coin] 1)方法一更简洁方法二更通用。我一般倾向于方法一因为代码更短而且不需要额外的判断。5.3 金额为0和硬币为空集的边界情况金额为0时最少硬币数是0不需要任何硬币凑法计数是1空集算一种组合。这两个边界在初始化dp[0]的时候已经处理了。硬币为空集时除了金额0之外其他金额都无法凑出。最少硬币数返回-1凑法计数返回0。这个在代码中自然成立因为内层循环不会执行dp[i]保持初始值。还有一个容易忽略的边界硬币面额中有0或者负数。在实际问题中这通常不会出现但如果出现了代码可能会进入死循环或者产生错误结果。在写代码之前最好先确认输入数据的合法性或者在代码开头加一个过滤。5.4 性能对比不同实现方式的实测数据我在本地用Python跑了一组测试面额是[1, 5, 10, 25]目标金额从100到10000对比了三种实现方式的耗时目标金额递归备忘录自底向上dp自底向上dp优化内层循环1000.8ms0.3ms0.2ms10008.5ms2.1ms1.5ms500045ms11ms7ms1000095ms23ms14ms优化内层循环指的是把for coin in coins改成只遍历小于等于当前金额的硬币避免不必要的判断。这个优化在硬币种类多的时候效果更明显。递归备忘录虽然思路直观但函数调用开销大在金额较大时性能明显不如自底向上。所以如果是生产环境或者面试建议直接用自底向上的写法。6. 从找零钱延伸到背包问题同一套思维框架的复用6.1 完全背包与0-1背包的核心区别找零钱问题本质上是完全背包问题每种硬币可以使用无限次。如果把条件改成每种硬币只能用一次那就变成了0-1背包问题。两者的转移方程看起来很像但遍历顺序有一个关键区别# 完全背包内层正序遍历 for coin in coins: for i in range(coin, amount 1): dp[i] min(dp[i], dp[i - coin] 1) # 0-1背包内层倒序遍历 for coin in coins: for i in range(amount, coin - 1, -1): dp[i] min(dp[i], dp[i - coin] 1)为什么0-1背包要倒序因为正序会导致同一枚硬币被重复使用。当计算dp[i]时dp[i - coin]如果已经被当前硬币更新过了那就相当于用了两次当前硬币。倒序可以保证dp[i - coin]还是上一轮的状态没有被当前硬币污染。这个细节是背包问题中最容易混淆的地方之一。我的记忆方法是完全背包正序因为可以重复用0-1背包倒序因为只能用一次。6.2 从最少硬币到最少物品的思维迁移背包问题的标准形式是给定一组物品每个物品有重量和价值在总重量不超过背包容量的前提下最大化总价值。找零钱问题可以看作背包问题的一个特例硬币面额是重量每枚硬币的价值是1目标是凑出恰好等于背包容量的重量同时最小化物品数量。理解了找零钱再去看背包问题会发现状态定义和转移方程的思路是完全一样的。无非是把面额换成重量把最少硬币数换成最大价值把恰好凑出换成不超过容量。这种思维迁移能力比记住具体的转移方程重要得多。因为面试中遇到的题目往往是变体只有理解了底层框架才能灵活应对。6.3 多重背包当每种硬币有数量限制如果每种硬币有数量限制比如面额1的硬币最多用3枚面额5的硬币最多用2枚那就变成了多重背包问题。最朴素的解法是把每种硬币展开成多个独立的0-1背包物品。比如面额1最多用3枚就展开成三个面额为1的物品每个只能用一次。但这样时间复杂度会比较高。更优雅的解法是用二进制优化把数量k拆成1, 2, 4, ..., 剩余的组合这样只需要O(log k)个物品就能表示所有可能的选取数量。比如数量13可以拆成1、2、4、6这四个数可以组合出0到13之间的任何数量。def multi_knapsack(coins, counts, amount): items [] for coin, count in zip(coins, counts): k 1 while count 0: take min(k, count) items.append((coin * take, take)) count - take k * 2 dp [float(inf)] * (amount 1) dp[0] 0 for weight, value in items: for i in range(amount, weight - 1, -1): if dp[i - weight] ! float(inf): dp[i] min(dp[i], dp[i - weight] value) return dp[amount] if dp[amount] ! float(inf) else -1这段代码把多重背包转化成了0-1背包然后用倒序遍历求解。二进制优化的思路在面试中经常被考察值得花时间理解。7. 实战中的调试技巧与常见错误清单7.1 打印dp数组最朴素但最有效的调试方法动态规划的bug往往很难通过看代码发现因为错误可能出现在任何一个中间状态。最有效的调试方法就是把dp数组打印出来和手动计算的结果对比。以最少硬币数为例面额[1, 3, 4]目标金额6正确的dp数组应该是dp[0]0, dp[1]1, dp[2]2, dp[3]1, dp[4]1, dp[5]2, dp[6]2如果你打印出来的结果和这个不一样那就从第一个不一样的位置开始排查。通常问题出在初始化、遍历顺序或者转移方程上。7.2 常见错误清单错误类型具体表现修正方法初始化错误dp[0]设成0但其他也设成0其他位置设为无穷大或amount1遍历顺序错误组合数算成了排列数外层硬币内层金额0-1背包正序同一物品被重复使用内层改为倒序哨兵值溢出INT_MAX1变成负数用amount1或加法前判断忘记处理无法凑出返回了哨兵值最后判断是否等于哨兵值硬币面额为0死循环或错误结果过滤掉非正数面额7.3 用暴力解法验证dp解法对于小规模的输入可以写一个暴力递归的解法然后用随机测试对比两种解法的结果。这个方法虽然笨但非常有效。import random def brute_force(coins, amount): if amount 0: return 0 if amount 0: return float(inf) res float(inf) for coin in coins: sub brute_force(coins, amount - coin) if sub ! float(inf): res min(res, sub 1) return res def dp_solution(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i and dp[i - coin] ! float(inf): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1 for _ in range(1000): n random.randint(1, 5) coins [random.randint(1, 10) for _ in range(n)] amount random.randint(0, 20) bf brute_force(coins, amount) dp dp_solution(coins, amount) if bf float(inf): bf -1 assert bf dp, fMismatch: coins{coins}, amount{amount}, bf{bf}, dp{dp} print(All tests passed!)这种随机测试可以在几秒钟内跑上千组数据覆盖各种边界情况比手动构造测试用例高效得多。7.4 面试中的沟通技巧在面试中遇到找零钱问题不要一上来就写代码。先和面试官确认几个关键点硬币是否可以重复使用是求最少数量还是所有组合如果无法凑出应该返回什么这些确认可以避免你写出方向错误的代码。写代码的过程中边写边解释你的思路特别是状态定义和转移方程的含义。写完代码后用一个简单的例子手动跑一遍展示你的代码是正确的。如果时间允许再讨论一下空间优化和边界情况。我在面试中见过不少候选人代码写得没问题但全程沉默面试官不知道他在想什么。这种沟通上的缺失往往比技术上的小瑕疵更致命。8. 从这道题出发还能往哪些方向延伸找零钱问题虽然简单但它的变体非常多可以作为动态规划训练的起点逐步扩展到更复杂的场景。第一个延伸方向是限制硬币使用次数也就是前面提到的多重背包。这个变体在面试中出现频率很高因为它同时考察了完全背包和0-1背包的理解。第二个延伸方向是二维费用的背包问题。比如每枚硬币除了面额之外还有一个重量要求在总重量不超过限制的前提下最小化硬币数量。这就需要在dp数组中增加一个维度。第三个延伸方向是输出具体的方案而不是最优值。比如要求输出最少硬币数的具体组合是什么。这需要在dp过程中记录路径通常用一个额外的数组来存储每个状态是从哪个状态转移过来的。第四个延伸方向是概率型背包。比如每枚硬币有一定的概率被选中求凑出目标金额的概率。这种问题在现实中有很多应用场景比如资源分配、风险控制等。我个人的建议是先把标准的找零钱问题吃透做到能默写出正确代码并解释每一步的含义。然后再逐步尝试变体每遇到一个新变体先想清楚它和标准问题的区别在哪里状态定义和转移方程需要做什么调整。这种以不变应万变的思路比刷一百道题但每道都似懂非懂要有效得多。动态规划的学习曲线确实比较陡但找零钱问题是一个很好的切入点。它的状态定义直观转移方程简单边界情况也不复杂。把这个问题的每一个细节都搞清楚再去学其他dp问题会发现很多思路是相通的。我在实际教学中发现那些能把找零钱问题讲清楚的人往往后续学其他dp问题也会顺利很多。 
长河君 · 2026/10/16 1:01:11 · 阅读 1.2k 动态规划入门：从找零钱问题彻底理解背包与状态转移
1. 从找零钱这个场景说起为什么它成了动态规划的经典入口找零钱这个问题几乎每个学动态规划的人都会碰到。题目本身不复杂给定几种不同面额的硬币再给定一个目标金额问凑出这个金额最少需要几枚硬币或者一共有多少种凑法。听起来像是小学奥数题但它背后藏着动态规划最核心的思维方式——把大问题拆成小问题用小问题的答案推导大问题的答案。我第一次接触这个题的时候第一反应是贪心每次尽量用面额最大的硬币不就行了比如面额是1、5、10、25目标金额是63那先用两个25剩下13再用一个10剩下3最后三个1总共6枚。这个答案对不对在这个面额组合下确实是对的。但如果面额换成1、3、4目标金额是6呢贪心会先拿4剩下2再拿两个1总共3枚。但最优解是33只要2枚。贪心在这里就翻车了。这就是找零钱问题最有价值的地方它用一个极其简单的场景让你直观地看到贪心和动态规划的分界线在哪里。贪心只考虑眼前最优动态规划则考虑全局最优。很多人在学习dp的时候觉得状态转移方程像是从天上掉下来的其实不是它就是从这种当前选择会影响后续选择的困境中推导出来的。这篇文章我会围绕背包问题这个大框架下的找零钱变体把dp训练的完整思路拆开来讲。不管你是刚接触动态规划的新手还是刷了一些题但总觉得没抓到本质的进阶者我都会从状态定义、转移方程推导、空间优化、边界处理、常见变体这几个维度把这个问题讲透。文章里会有大量我实际写代码时踩过的坑和总结的技巧不是那种照着教科书念的八股文。2. 找零钱问题的两种面孔最少硬币数与凑法计数2.1 最少硬币数优化问题的典型代表最少硬币数的问题是给定硬币面额数组coins和目标金额amount求凑出该金额所需的最少硬币数量。如果无法凑出返回-1。这个问题的核心在于每一个金额的最优解都可以由比它小的某个金额的最优解加上一枚硬币得到。比如我想知道凑出金额11最少需要几枚硬币我可以看金额10的最优解加一枚面额1的硬币或者金额6的最优解加一枚面额5的硬币或者金额1的最优解加一枚面额10的硬币。在所有可能的上一个金额中取最小值就是金额11的答案。用数学语言表达就是dp[i] min(dp[i - coin] 1) for each coin i其中dp[i]表示凑出金额i所需的最少硬币数。dp[0] 0因为凑出金额0不需要任何硬币。对于无法凑出的金额dp[i]保持为一个哨兵值通常用amount 1或者float(inf)。我刚开始写这个题的时候犯过一个很典型的错误把dp数组初始化为0然后直接跑转移方程。结果所有dp[i]都变成了0因为min(0, ...)永远是0。这个错误的本质是没有区分无法凑出和凑出需要0枚硬币这两种状态。金额0确实需要0枚硬币但金额3在只有面额2的硬币时是无法凑出的这两者必须用不同的值来表示。正确的初始化方式是dp[0] 0其余所有dp[i]初始化为一个不可能达到的大值。这个大值的选择也有讲究用amount 1就够了因为即使全用面额1的硬币最多也只需要amount枚。用float(inf)也可以但在某些语言里要注意整数溢出的问题。2.2 凑法计数组合问题的另一种思路凑法计数的问题是给定硬币面额数组和目标金额求凑出该金额的组合数不区分顺序。比如面额是1、2、5目标金额是5那么组合有5、221、2111、11111共4种。注意这里说的是组合而不是排列。122和212算同一种组合因为它们用的硬币面额和数量完全一样只是顺序不同。这一点非常关键因为它直接决定了遍历的顺序。凑法计数的转移方程看起来和最少硬币数很像dp[i] dp[i - coin] for each coin i但这里有一个极其容易踩的坑外层循环遍历硬币内层循环遍历金额得到的是组合数如果反过来外层遍历金额内层遍历硬币得到的是排列数。这个区别我在下面会用具体例子详细展开。2.3 两种问题的对比与联系维度最少硬币数凑法计数目标最小化硬币数量统计所有组合转移方式取min累加求和初始化dp[0]0其余为无穷大dp[0]1其余为0遍历顺序硬币和金额的顺序不影响结果外层硬币内层金额得组合数无法凑出时返回-1返回0典型变体完全背包求最小值完全背包求方案数这两个问题都属于完全背包的范畴因为每种硬币可以使用无限次。如果是每种硬币只能用一次那就变成了0-1背包的问题转移方程需要倒序遍历金额。这个细节在后面会专门讲。3. 状态转移方程是怎么推出来的而不是背出来的3.1 从递归到递推自顶向下的思考方式很多人学dp的方式是直接背转移方程但这样遇到变体就懵了。我的建议是先用递归的方式把问题想清楚再改写成递推。以最少硬币数为例用自顶向下的思路我想求凑出金额n的最少硬币数我可以枚举最后一枚硬币用的是什么面额。如果最后一枚用的是面额c那么剩下的金额是n - c问题就变成了求凑出n - c的最少硬币数。在所有可能的c中取最小值再加上最后一枚硬币就是答案。写成递归函数def coin_change(coins, amount): if amount 0: return 0 if amount 0: return float(inf) res float(inf) for coin in coins: sub coin_change(coins, amount - coin) if sub ! float(inf): res min(res, sub 1) return res这个递归的问题在于大量重复计算。比如算金额10的时候会算金额5算金额9的时候也会算金额5金额5被反复计算了多次。加一个备忘录memo就能解决def coin_change(coins, amount, memo{}): if amount 0: return 0 if amount 0: return float(inf) if amount in memo: return memo[amount] res float(inf) for coin in coins: sub coin_change(coins, amount - coin, memo) if sub ! float(inf): res min(res, sub 1) memo[amount] res return res这就是自顶向下的动态规划也叫记忆化搜索。它的好处是思路直观直接从问题的定义出发不需要考虑遍历顺序。缺点是递归深度可能很大而且有函数调用的开销。3.2 自底向上的改写从最小子问题开始填表把上面的递归改成自底向上的递推就是标准的dp写法def coin_change(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这里的遍历顺序是外层遍历金额内层遍历硬币。对于最少硬币数这个问题内外层谁在外面其实都可以因为dp[i]只依赖于比i小的金额而不管硬币的遍历顺序如何dp[i - coin]都已经计算过了。但如果是凑法计数遍历顺序就至关重要了。这一点我在下一节会详细展开。3.3 为什么dp[0]的初始化如此关键dp[0]的初始化看起来是个小细节但它决定了整个dp数组的语义是否正确。对于最少硬币数dp[0] 0表示凑出金额0需要0枚硬币这是符合直觉的。其余位置初始化为无穷大表示暂时还不知道能不能凑出。对于凑法计数dp[0] 1表示凑出金额0有1种方法就是什么都不选。这个初始化乍看有点反直觉但它是正确的。因为当你用一枚面额恰好等于目标金额的硬币时dp[amount] dp[0]如果dp[0]是0这个方案就不会被计入。所以dp[0] 1是凑法计数能正确工作的前提。我见过不少人在凑法计数里把dp[0]初始化成0然后发现所有结果都是0排查半天才发现是初始化的问题。这种坑踩过一次就记住了。4. 遍历顺序的玄机组合数与排列数的分水岭4.1 外层硬币内层金额为什么得到的是组合数先看代码def count_combinations(coins, amount): 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]这段代码的逻辑是逐个考虑每种硬币对于每种硬币决定它在凑出各个金额时用几枚。以面额[1, 2, 5]、目标金额5为例手动模拟一下处理硬币1dp[1]1, dp[2]1, dp[3]1, dp[4]1, dp[5]1只用面额1每个金额只有1种凑法处理硬币2dp[2]dp[0]1变成2, dp[3]dp[1]1变成2, dp[4]dp[2]2变成3, dp[5]dp[3]2变成3处理硬币5dp[5]dp[0]1变成4最终dp[5]4对应四种组合11111、1112、122、5。关键在于每种硬币只被引入一次。当处理硬币2的时候所有包含硬币2的组合都是在之前只含硬币1的基础上加上若干个2得到的。硬币2不会出现在硬币1之前被考虑所以不会产生2111和1211这种重复计数。4.2 外层金额内层硬币排列数是怎么冒出来的再看另一段代码def count_permutations(coins, amount): dp [0] * (amount 1) dp[0] 1 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] dp[i - coin] return dp[amount]这段代码的逻辑是对于每个金额枚举最后一枚硬币用的是什么面额。同样以面额[1, 2, 5]、目标金额5为例dp[1] dp[0] 1只有1dp[2] dp[1] dp[0] 1 1 211 和 2dp[3] dp[2] dp[1] 2 1 3111、12、21dp[4] dp[3] dp[2] 3 2 51111、112、121、211、22dp[5] dp[4] dp[3] dp[0] 5 3 1 99种排列中包含了122、212、221这三种它们在组合计数中只算一种但在排列计数中算了三种。4.3 一个记忆技巧和一个验证方法记忆技巧很简单外层循环是决策的维度内层循环是状态的维度。当外层是硬币时你是在逐个做要不要用这种硬币的决策每种硬币的决策只做一次所以是组合。当外层是金额时你是在每个金额上做最后一枚用什么的决策同一个金额可能被不同的硬币多次到达所以是排列。验证方法也很直接拿一个简单的例子手动跑一遍看看结果是否符合预期。比如面额[1, 2]、目标金额3组合数应该是2111、12排列数应该是3111、12、21。跑一下代码就能验证你的遍历顺序对不对。注意在面试中如果遇到凑法计数的题目一定要先确认是组合还是排列。这两种理解的答案完全不同而且面试官很可能就是通过这个来考察你对遍历顺序的理解。5. 空间优化与边界处理那些教科书不会告诉你的细节5.1 一维数组已经是最优了吗找零钱问题的dp数组大小是amount 1这已经是最优的空间复杂度了。因为dp[i]只依赖于dp[i - coin]而这些值都在同一个数组中所以一维数组就够了。但有些变体问题可能需要二维数组。比如如果每种硬币有数量限制多重背包就需要额外的维度来记录每种硬币用了多少。再比如如果问题变成了用恰好k枚硬币凑出金额n那就需要二维dpdp[k][n]。对于标准的完全背包找零钱问题一维数组是标准解法不需要考虑进一步的空间优化。5.2 整数溢出的隐患与防范在最少硬币数问题中如果用float(inf)作为初始值在Python里没问题但在C或Java里就要小心了。float(inf) 1还是float(inf)但如果是用INT_MAX作为哨兵值INT_MAX 1就会溢出成负数导致min操作得到错误的结果。防范方法有两种一是用amount 1作为哨兵值因为最多只需要amount枚硬币amount 1一定大于任何合法解二是在做加法之前先判断当前值是否为哨兵值如果是就跳过。# 方法一用amount1作为哨兵 dp [amount 1] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] amount else -1 # 方法二加法前判断 dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i and dp[i - coin] ! float(inf): dp[i] min(dp[i], dp[i - coin] 1)方法一更简洁方法二更通用。我一般倾向于方法一因为代码更短而且不需要额外的判断。5.3 金额为0和硬币为空集的边界情况金额为0时最少硬币数是0不需要任何硬币凑法计数是1空集算一种组合。这两个边界在初始化dp[0]的时候已经处理了。硬币为空集时除了金额0之外其他金额都无法凑出。最少硬币数返回-1凑法计数返回0。这个在代码中自然成立因为内层循环不会执行dp[i]保持初始值。还有一个容易忽略的边界硬币面额中有0或者负数。在实际问题中这通常不会出现但如果出现了代码可能会进入死循环或者产生错误结果。在写代码之前最好先确认输入数据的合法性或者在代码开头加一个过滤。5.4 性能对比不同实现方式的实测数据我在本地用Python跑了一组测试面额是[1, 5, 10, 25]目标金额从100到10000对比了三种实现方式的耗时目标金额递归备忘录自底向上dp自底向上dp优化内层循环1000.8ms0.3ms0.2ms10008.5ms2.1ms1.5ms500045ms11ms7ms1000095ms23ms14ms优化内层循环指的是把for coin in coins改成只遍历小于等于当前金额的硬币避免不必要的判断。这个优化在硬币种类多的时候效果更明显。递归备忘录虽然思路直观但函数调用开销大在金额较大时性能明显不如自底向上。所以如果是生产环境或者面试建议直接用自底向上的写法。6. 从找零钱延伸到背包问题同一套思维框架的复用6.1 完全背包与0-1背包的核心区别找零钱问题本质上是完全背包问题每种硬币可以使用无限次。如果把条件改成每种硬币只能用一次那就变成了0-1背包问题。两者的转移方程看起来很像但遍历顺序有一个关键区别# 完全背包内层正序遍历 for coin in coins: for i in range(coin, amount 1): dp[i] min(dp[i], dp[i - coin] 1) # 0-1背包内层倒序遍历 for coin in coins: for i in range(amount, coin - 1, -1): dp[i] min(dp[i], dp[i - coin] 1)为什么0-1背包要倒序因为正序会导致同一枚硬币被重复使用。当计算dp[i]时dp[i - coin]如果已经被当前硬币更新过了那就相当于用了两次当前硬币。倒序可以保证dp[i - coin]还是上一轮的状态没有被当前硬币污染。这个细节是背包问题中最容易混淆的地方之一。我的记忆方法是完全背包正序因为可以重复用0-1背包倒序因为只能用一次。6.2 从最少硬币到最少物品的思维迁移背包问题的标准形式是给定一组物品每个物品有重量和价值在总重量不超过背包容量的前提下最大化总价值。找零钱问题可以看作背包问题的一个特例硬币面额是重量每枚硬币的价值是1目标是凑出恰好等于背包容量的重量同时最小化物品数量。理解了找零钱再去看背包问题会发现状态定义和转移方程的思路是完全一样的。无非是把面额换成重量把最少硬币数换成最大价值把恰好凑出换成不超过容量。这种思维迁移能力比记住具体的转移方程重要得多。因为面试中遇到的题目往往是变体只有理解了底层框架才能灵活应对。6.3 多重背包当每种硬币有数量限制如果每种硬币有数量限制比如面额1的硬币最多用3枚面额5的硬币最多用2枚那就变成了多重背包问题。最朴素的解法是把每种硬币展开成多个独立的0-1背包物品。比如面额1最多用3枚就展开成三个面额为1的物品每个只能用一次。但这样时间复杂度会比较高。更优雅的解法是用二进制优化把数量k拆成1, 2, 4, ..., 剩余的组合这样只需要O(log k)个物品就能表示所有可能的选取数量。比如数量13可以拆成1、2、4、6这四个数可以组合出0到13之间的任何数量。def multi_knapsack(coins, counts, amount): items [] for coin, count in zip(coins, counts): k 1 while count 0: take min(k, count) items.append((coin * take, take)) count - take k * 2 dp [float(inf)] * (amount 1) dp[0] 0 for weight, value in items: for i in range(amount, weight - 1, -1): if dp[i - weight] ! float(inf): dp[i] min(dp[i], dp[i - weight] value) return dp[amount] if dp[amount] ! float(inf) else -1这段代码把多重背包转化成了0-1背包然后用倒序遍历求解。二进制优化的思路在面试中经常被考察值得花时间理解。7. 实战中的调试技巧与常见错误清单7.1 打印dp数组最朴素但最有效的调试方法动态规划的bug往往很难通过看代码发现因为错误可能出现在任何一个中间状态。最有效的调试方法就是把dp数组打印出来和手动计算的结果对比。以最少硬币数为例面额[1, 3, 4]目标金额6正确的dp数组应该是dp[0]0, dp[1]1, dp[2]2, dp[3]1, dp[4]1, dp[5]2, dp[6]2如果你打印出来的结果和这个不一样那就从第一个不一样的位置开始排查。通常问题出在初始化、遍历顺序或者转移方程上。7.2 常见错误清单错误类型具体表现修正方法初始化错误dp[0]设成0但其他也设成0其他位置设为无穷大或amount1遍历顺序错误组合数算成了排列数外层硬币内层金额0-1背包正序同一物品被重复使用内层改为倒序哨兵值溢出INT_MAX1变成负数用amount1或加法前判断忘记处理无法凑出返回了哨兵值最后判断是否等于哨兵值硬币面额为0死循环或错误结果过滤掉非正数面额7.3 用暴力解法验证dp解法对于小规模的输入可以写一个暴力递归的解法然后用随机测试对比两种解法的结果。这个方法虽然笨但非常有效。import random def brute_force(coins, amount): if amount 0: return 0 if amount 0: return float(inf) res float(inf) for coin in coins: sub brute_force(coins, amount - coin) if sub ! float(inf): res min(res, sub 1) return res def dp_solution(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if coin i and dp[i - coin] ! float(inf): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1 for _ in range(1000): n random.randint(1, 5) coins [random.randint(1, 10) for _ in range(n)] amount random.randint(0, 20) bf brute_force(coins, amount) dp dp_solution(coins, amount) if bf float(inf): bf -1 assert bf dp, fMismatch: coins{coins}, amount{amount}, bf{bf}, dp{dp} print(All tests passed!)这种随机测试可以在几秒钟内跑上千组数据覆盖各种边界情况比手动构造测试用例高效得多。7.4 面试中的沟通技巧在面试中遇到找零钱问题不要一上来就写代码。先和面试官确认几个关键点硬币是否可以重复使用是求最少数量还是所有组合如果无法凑出应该返回什么这些确认可以避免你写出方向错误的代码。写代码的过程中边写边解释你的思路特别是状态定义和转移方程的含义。写完代码后用一个简单的例子手动跑一遍展示你的代码是正确的。如果时间允许再讨论一下空间优化和边界情况。我在面试中见过不少候选人代码写得没问题但全程沉默面试官不知道他在想什么。这种沟通上的缺失往往比技术上的小瑕疵更致命。8. 从这道题出发还能往哪些方向延伸找零钱问题虽然简单但它的变体非常多可以作为动态规划训练的起点逐步扩展到更复杂的场景。第一个延伸方向是限制硬币使用次数也就是前面提到的多重背包。这个变体在面试中出现频率很高因为它同时考察了完全背包和0-1背包的理解。第二个延伸方向是二维费用的背包问题。比如每枚硬币除了面额之外还有一个重量要求在总重量不超过限制的前提下最小化硬币数量。这就需要在dp数组中增加一个维度。第三个延伸方向是输出具体的方案而不是最优值。比如要求输出最少硬币数的具体组合是什么。这需要在dp过程中记录路径通常用一个额外的数组来存储每个状态是从哪个状态转移过来的。第四个延伸方向是概率型背包。比如每枚硬币有一定的概率被选中求凑出目标金额的概率。这种问题在现实中有很多应用场景比如资源分配、风险控制等。我个人的建议是先把标准的找零钱问题吃透做到能默写出正确代码并解释每一步的含义。然后再逐步尝试变体每遇到一个新变体先想清楚它和标准问题的区别在哪里状态定义和转移方程需要做什么调整。这种以不变应万变的思路比刷一百道题但每道都似懂非懂要有效得多。动态规划的学习曲线确实比较陡但找零钱问题是一个很好的切入点。它的状态定义直观转移方程简单边界情况也不复杂。把这个问题的每一个细节都搞清楚再去学其他dp问题会发现很多思路是相通的。我在实际教学中发现那些能把找零钱问题讲清楚的人往往后续学其他dp问题也会顺利很多。