1. 硬币问题里藏着动态规划的哪几层考点这期继续聊动态规划系列这次的主角是两类出场率极高的经典问题最少硬币和所有硬币问题。如果你刷过LeetCode或者校招笔试题大概率遇到过这类题给定几种面值的硬币每种硬币无限量供应让你凑出一个目标金额。题目可能问“最少需要几枚硬币”可能问“一共有多少种凑法”也可能问“把具体凑法全部列出来”。先说一个很重要的判断硬币问题看起来是“货币场景”实际上它的底层逻辑是一个完全背包问题。还记得系列前两篇讲过的0-1背包吗0-1背包里每件物品最多取一次而硬币题的每种硬币不限制次数所以你拿到的递推关系和代码模板本质上是从完全背包演化过来的。理解了这层关系你就不会觉得硬币问题是孤立的知识点而会把它归类成给定物品集合与容量物品可重复选取求最优值或方案数。硬币问题常见的问法我整理了一下基本覆盖了所有考法最少硬币数目标金额固定每枚硬币有面值求组成目标金额所需的最小硬币数量。这是最基础的考法代表题是LeetCode 322。硬币组合总数目标金额固定求一共有多少种不同的组合方式代表题是LeetCode 518。输出全部组合方案不只要数量还要把所有硬币组合打印出来考察回溯剪枝与dp回溯还原。有限硬币的情况每种硬币有数量限制变成了多重背包或者要用二进制分组优化。排列与组合的区别有些题要求顺序不同的算不同方案比如LeetCode 377这个特容易踩坑。也就是说“最少硬币和所有硬币问题”这个标题下其实涵盖了至少三层递进第一层是数量最优第二层是方案计数第三层是方案还原。前两层在笔试面试里极高频第三层虽然考得少但它是检验你“是不是真的理解dp过程”的试金石。这篇文章我会从暴力递归开始讲一直推进到一维dp、方案计数、回溯还原完整路径最后补充几个必须注意的边界坑。不管你是刚开始学动态规划的小白还是已经会套模板但说不清原理的进阶选手这篇都值得仔细过一遍。2. 暴力递归为什么会超时所有硬币问题的逻辑根源2.1 从无序列举到递推公式先不要急着写dp数组我们从没有任何优化的问题本身出发看看硬币问题本质上是什么。假设硬币面值是 [1, 3, 5] 目标金额是 11。最少硬币数的直观做法是什么你可能想优先用大面值的5 5 1一共3枚。但这不是所有情况的最优解。比如面值是 [1, 3, 4] 目标金额是 6贪心会选 4 1 1共3枚但最优其实是 3 3只需2枚。这说明什么说明硬币问题不能用贪心必须把所有可能的分法都尝试一遍才能确保找到最小值。既然要穷举所有分法我们能不能用一个函数来描述“凑出金额x最少需要几枚硬币”当然可以。设f(x)表示凑出金额 x 的最少硬币数那么最后一个硬币可能是任意一种面值于是状态转移公式就出来了f(x) min( f(x - coins[0]) 1, f(x - coins[1]) 1, ..., f(x - coins[n-1]) 1 )也就是说我先假装“最后一枚硬币面值是 coin”那么前面凑出x - coin的部分就是规模更小的子问题。这个递推关系是所有硬币问题的根后面的dp数组、记忆化、滚动优化全是围绕它展开的。2.2 递归树爆炸的直观感受用递归去实现上面这个函数代码很短但我劝你不要在真实场景里直接跑。我们来分析一下它的复杂度。以面值 [1, 3, 5] 、目标 11 为例。调用f(11)会分别去算f(10)、f(8)、f(6)。而f(10)又会去算f(9)、f(7)、f(5)。你会发现f(6)在f(11)这一层就被算了一次之后在f(8)、f(9)、f(7)的子调用里还会被反复计算无数遍。这就像你整理房间时把一个文件夹翻了十遍每次翻完又放回去下个任务再重新翻一遍时间全浪费在做重复事情上了。递归树的分支因子是硬币种类数 k递归深度大约是目标金额 / 最小硬币面值所以最坏情况下复杂度是 O(k^n) 级别的指数爆炸金额稍微大一点就直接卡死。2.3 这给了我们什么启示暴力递归虽然效率低但它给了我们正确答案的定义而且是后面所有优化的“母版”。你在学习动态规划时一定要养成的习惯是先写出暴力递归再去分析哪些子问题是重复计算的然后用记忆化或者自底向上的方式干掉重复计算。很多同学一上来就背dp[j] min(dp[j], dp[j - coin] 1)这个状态转移却不知道它从哪来一旦题目稍微变形比如要求方案数、要求打印路径、要求排列数就懵了。所以这一节的内容看着基础实际上是最重要的地基。3. 记忆化搜索在递归树上做缓存3.1 如何把重复计算缓存起来既然递归的问题在于反复计算相同的f(x)那最简单的优化方式是加一个缓存表把已经算过的f(x)存下来下次直接查表返回。在Python里可以用lru_cache装饰器也可以自己写一个字典或列表。记忆化搜索的代码逻辑和递归几乎一样唯一的区别是函数开头先查缓存递归结束把结果写进缓存。我用Python写一个例子from functools import lru_cache from typing import List def coin_change_memo(coins: List[int], amount: int) - int: lru_cache(None) def f(x: int) - int: if x 0: return 0 if x 0: return float(inf) ans float(inf) for coin in coins: ans min(ans, f(x - coin) 1) return ans res f(amount) return -1 if res float(inf) else res这里我额外处理了x 0的情况如果某个硬币面值大于当前剩余金额那这条路走不通返回正无穷。正无穷在后面的比较中会被自然过滤掉。这样写代码能极大减少重复计算但有没有发现一个问题我们在递归过程中频繁使用函数调用Python的函数调用开销并不小而且lru_cache本身也有哈希计算成本。所以记忆化搜索在实际比赛里能过大部分题但不够极致。从学习角度记忆化搜索和自底向上的dp表达的是同一个递推关系区别只是计算的顺序。这一篇既然是系列第三篇我默认前面的内容已经讲透了 dp 数组的构建方法所以这一节只简单带过重点放在下一节的完全背包套路上。3.2 为什么我建议你从记忆化过渡到dp记忆化搜索最大的优点是思考负担小它顺着自然递归去写不容易漏掉状态。但它有两个问题一是递归深度Python默认递归深度是1000左右如果金额很大递归链很长会直接报RecursionError二是它没有把状态压缩的潜力发挥出来。你仔细看递推公式会发现f(x)只依赖比 x 更小的状态既然依赖方向是确定的我们完全可以用一个循环从小到大把状态算出来这就是自底向上的dp。所以我的建议是新手先用记忆化搜索写一版验证递推公式是否正确然后再考虑改写成dp数组最后再套一维滚动优化。这样一步一步来既不会出错也能真正理解为什么要用dp。4. 自底向上的dp数组状态定义与遍历方向一个都不能错4.1 明确dp数组的含义自底向上的思路很直接用一个数组dp[i]表示凑出金额 i 所需的最少硬币数。那么显然有边界条件dp[0] 0因为凑0块钱不需要任何硬币。其他金额初始化为一个很大的数表示“还没找到可行方案”。状态转移公式和递归时的公式一模一样dp[i] min(dp[i], dp[i - coin] 1) for coin in coins但遍历顺序很关键这里的门道决定了你是“完全背包”还是“多重背包”是“排列数”还是“组合数”。4.2 为什么一维数组里外层循环硬币、内层循环金额在完全背包场景下每种硬币可以取无限次所以我们需要在同一个硬币面值上反复更新dp值允许同一个硬币被多次使用。内层循环金额时必须从头向尾正向遍历def coin_change_least(coins: List[int], amount: int) - int: dp [float(inf)] * (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] float(inf) else dp[amount]注意我这里的写法是外层硬币、内层金额、内层正序。如果是0-1背包内层必须倒序遍历防止同一件物品被重复选取。但硬币题是无限量供应所以正序才是正确的。这个区别一定要在脑子里刻下来。那我问你一个问题如果把内外层循环换一下也就是外层金额、内层硬币会怎样结果会变吗对于“最少硬币数”这个问题答案是不变因为min运算满足交换律无论先尝试哪个硬币取最小值都一样。但对于下一节要讲的“方案数”循环顺序就至关重要了它决定你算的是组合数还是排列数。4.3 一个完整例子手算过程我们用一个具体的例子来验证上面的代码逻辑。硬币面值 [1, 3, 5] 目标金额 8。初始化dp [0, inf, inf, inf, inf, inf, inf, inf, inf]第一轮coin 1从头到尾更新i1: dp[1] min(inf, dp[0]1) 1i2: dp[2] min(inf, dp[1]1) 2i3: dp[3] min(inf, dp[2]1) 3... 一直到 dp[8] 8此时全部用1元硬币得到一种可行方案。第二轮coin 3i3: dp[3] min(3, dp[0]1) 1i4: dp[4] min(4, dp[1]1) 2i5: dp[5] min(5, dp[2]1) 3这里 dp[2]2 是上一轮用1元硬币的结果i6: dp[6] min(6, dp[3]1) 2dp[3] 刚刚被更新为1所以可以用33凑出6i7: dp[7] min(7, dp[4]1) 3i8: dp[8] min(8, dp[5]1) 4第三轮coin 5i5: dp[5] min(3, dp[0]1) 1i6: dp[6] min(2, dp[1]1) 2i7: dp[7] min(3, dp[2]1) 3i8: dp[8] min(4, dp[3]1) 2最终 dp[8] 2方案是 3 5。这个手算过程建议你跟着走一遍走完你对“滚动数组到底在滚动什么”会有非常直观的体会dp[i - coin] 可能是这一轮刚刚更新的值也可能保留了上一轮的值完全背包正因为允许这种“本轮更新继续参与后续更新”的机制才能实现硬币重复使用。5. 最少硬币与组合方案数的联合求解dp数组还能承载更多信息5.1 求组合总数时循环顺序决定命运如果你问“凑出目标金额一共有多少种组合方式”代码框架立刻就不一样了。先定义状态dp[i]表示凑出金额 i 的方案总数。边界条件是dp[0] 1因为凑0元只有一种方案——什么都不用。求方案数的状态转移是加法dp[i] dp[i - coin]但循环顺序必须格外小心。如果外层循环金额、内层循环硬币那么得到的是排列数因为每个金额都会重新遍历所有硬币等价于在每一步考虑最后一枚硬币是谁顺序不同的组合会被重复计数。如果外层循环硬币、内层循环金额那么硬币的加入顺序被固定得到的是组合数。我写一个对比示例面值 [1, 2] 目标 3外层硬币、内层金额组合数初始化 dp [1, 0, 0, 0]coin1: dp[1]dp[0]1, dp[2]dp[1]1, dp[3]dp[2]1得到 dp[1,1,1,1]表示 {1}、{1,1}、{1,1,1}coin2: dp[2]dp[0]2, dp[3]dp[1]2最终 dp[3]2方案是 {1,1,1} 和 {1,2}外层金额、内层硬币排列数i1: dp[1] dp[0] 1用1dp[1] 无法用2i2: dp[2] dp[1] 1用1dp[2] dp[0] 2用2i3: dp[3] dp[2] 2用1dp[3] dp[1] 3用2最终 dp[3]3方案是 {1,1,1}、{1,2}、{2,1}注意 {1,2} 和 {2,1} 被当作两种。LeetCode 322 求最少硬币数时min运算的交换律帮你掩盖了循环顺序的影响但一旦换成加法的方案计数循环顺序立刻暴露它的威力。这也是很多人“看得懂代码但一到变体题就懵”的根源他压根不知道循环顺序在这里决定了排列还是组合。5.2 在同一个dp里同时维护硬币数和方案数有时候题目不满足于只问最少硬币数可能要求输出“达到最少硬币数时的方案数量”。这时候不能只维护一个数组而是要维护两个数组min_coins[i]表示凑出金额 i 所需的最少硬币数count[i]表示在达到这个最少硬币数前提下的方案总数。状态转移时需要分情况讨论如果用某个硬币能得到更小的硬币数就更新min_coins同时count置为新状态的数量。如果得到的硬币数和当前最小硬币数相等就累加方案数。如果比当前的还大就跳过。代码示例def least_coins_and_count(coins: List[int], amount: int): INF float(inf) min_coins [INF] * (amount 1) count [0] * (amount 1) min_coins[0] 0 count[0] 1 for coin in coins: for i in range(coin, amount 1): # 使用这枚硬币后需要的硬币数为 min_coins[i-coin] 1 candidate min_coins[i - coin] 1 if candidate min_coins[i]: min_coins[i] candidate count[i] count[i - coin] elif candidate min_coins[i]: count[i] count[i - coin] if min_coins[amount] INF: return -1, 0 return min_coins[amount], count[amount]注意这里为什么要用count[i-coin]而不是count[i] something因为方案数是基于子问题的数量组合起来的。如果min_coins[i-coin]是凑出剩余金额的最优解那么用当前硬币补齐后整个方案数继承子问题的方案数如果有多个不同子问题都能达到同样的最优硬币数就累加它们的方案数。5.3 这个联合数组的实际应用场景你可能觉得这种“既要硬币数又要方案数”的题目很少见但实际上它经常出现在游戏策划的数值系统里。比如一个抽卡系统里道具可以用不同币种组合兑换策划需要知道最少消耗几个道具能兑换某件商品同时还想知道在最少消耗的方案里一共有多少种搭配方便设计成就任务。抛开游戏场景不少大厂的笔试环也出过类似的变体本质就是这一段说的双状态dp。6. 打印具体硬币组合从“数量”到“方案”的进阶6.1 为什么不能只靠dp数组还原前面我们通过dp求出了最少硬币数比如面值 [1, 3, 4] 、目标 6dp[6] 2方案是 3 3。如果你拿到dp数组之后想还原路径最直观的做法是从dp[amount]往前回溯看最后一枚硬币可能是哪个面值。具体来说对于一个状态 i如果硬币面值 coin 满足dp[i - coin] 1 dp[i]那么说明从 i-coin 这个状态加上 coin 可以到达最优状态 i。于是可以从 i 回溯到 i-coin再继续往前找。这样一路回溯直到 i 变成 0就得到了一条完整的硬币组合路径。但这里面有一个坑满足dp[i - coin] 1 dp[i]的 coin 可能不止一个这意味着最优方案可能有多条。如果你只在回溯时取第一个满足条件的硬币那你只会输出其中一条方案如果题目要求输出全部组合就需要在回溯过程中递归枚举所有可能的 coin。6.2 回溯输出全部组合的代码实现这一步才是“所有硬币问题”的完整形态。我们用递归枚举所有满足条件的转移from typing import List def print_all_solutions(coins: List[int], amount: int) - List[List[int]]: dp [float(inf)] * (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) if dp[amount] float(inf): return [] res [] path [] def dfs(remain: int): if remain 0: res.append(path[:]) return for coin in coins: # 剪枝硬币面值不能超过剩余金额且必须是最优转移 if coin remain and dp[remain - coin] 1 dp[remain]: path.append(coin) dfs(remain - coin) path.pop() dfs(amount) return res coins [1, 3, 4] amount 6 print(print_all_solutions(coins, amount)) # 输出 [[3, 3], [4, 1, 1]] 等可能结果具体顺序取决于硬币遍历顺序这里有个细节值得注意dfs 中的循环是遍历所有硬币并且用dp[remain - coin] 1 dp[remain]这个条件来判断当前硬币是否能作为最优路径的一部分。这个条件的含义是在目标金额 remain 的最优状态中如果减去 coin 后的子问题状态也是最优的那就说明 coin 可以放在这条路径上。为什么这个条件不会漏解因为dp是完全背包正序更新来的dp[remain]一定等于某个dp[remain - coin] 1所以最后一枚硬币一定藏在coins里。我们从后往前递归枚举就能把所有最优路径都找出来。复杂度方面要心里有数如果最优方案数非常多递归栈会很长输出结果本身就会爆炸。比如面值 [1] 目标 100最优方案只有1种但递归深度100如果面值组合让方案数呈指数增长输出所有方案本身就不可能做到多项式复杂度。所以在实际工程项目里除非题目明确要求输出全部组合而且数据范围很小否则不要这么枚举笔试里如果遇到这种题基本上输出配置很小目的是考察你的回溯能力而不是真的让你挑战天文数字的方案数。6.3 如果只是想输出一条路径很多时候不需要全部方案只需要给出任意一条最少硬币组合。那你可以用父节点记录法在dp更新的同时用一个last_coin[i]数组记录“第一次达到最优状态时用的最后一枚硬币”然后从 amount 一路回溯到0把硬币倒序收集起来。代码写起来更轻量def print_one_solution(coins: List[int], amount: int) - List[int]: dp [float(inf)] * (amount 1) last_coin [0] * (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 last_coin[i] coin if dp[amount] float(inf): return [] res [] cur amount while cur 0: coin last_coin[cur] res.append(coin) cur - coin return res可以看到区别维护last_coin[i]只需要一个一维数组回溯时也不用递归一个while循环就搞定了。代价是它丢失了多解的信息只保留“最后被更新”的那一个硬币来源。6.4 关于回溯顺序的直觉解释你可能会好奇回溯时从大到小还是从小到大遍历硬币对结果有什么影响这会影响组合在输出里的排列顺序。如果先把大面值硬币放前面输出方案会倾向于大面值在前的组合如果从小到大输出方案会以“尽量多使用小面值硬币”的方式出现。这一点对结果正确性没有任何影响但会让输出看起来更直观。面试时如果能意识到这一点并且主动解释给面试官听会是很加分的表现。7. 边界情况和易错点这些坑我全踩过7.1 凑不出的金额怎么处理这是最容易让人翻车的点。有些硬币组合无论如何都凑不出目标金额比如硬币面值是 [2, 4] 目标金额是 5这时候 dp[5] 将保持初始化的无穷大或一个很大的值。在返回时一定要判断dp[amount]是否还是无穷大如果是返回 -1最少硬币题或 0方案数题。有个更隐蔽的问题初始化时如果直接把 dp 数组设为float(inf)在Python里没问题但在 Java 或 C 里如果你用Integer.MAX_VALUE做哨兵然后执行dp[i - coin] 1一旦dp[i-coin]恰好也是MAX_VALUE整体会溢出变成负数导致比较逻辑全乱。解决办法是用一个相对安全的哨兵比如amount 1或者Integer.MAX_VALUE / 2。既然这是一个现金意义上的问题在工程代码里我习惯用一个足够大的有限值比如10**9而不是真正的无穷大。7.2 金额为0时的边界答案这是笔试题里最高频的边界测试点。目标金额为0时最少硬币数是0方案数是1具体方案是空列表。很多人在求方案数时把dp[0]初始化为0结果出来永远是0这就是初始化错误。再次强调dp[0]1表示空组合这一种方案它是最小状态是一切计数的基础没有它后面的dp[i] dp[i-coin]永远加不出任何东西。7.3 硬币面值大于目标金额的情况如果硬币面值比目标金额还大比如 goal 是 5硬币里有 10那么在更新时i从 coin 开始循环10这一枚永远不会参与计算因为内层循环i的范围只到 amount。这个不算bug但有些同学会因为“为什么答案没用到这枚硬币”而产生困惑。记住dp数组的长度只到 amount比它大的面值在这一次计算里天然被忽略。7.4 硬币数组里有重复面值怎么办这得分情况。如果题目给的是多枚不同币种但面值相同比如 [1, 1, 3]在组合数问题上两个面值1的硬币会被当作不同的来源方案数会翻倍。LeetCode 518 这类题通常默认面值不同但实际工程中如果上游数据脏可能混入重复面值。处理办法是预处理去重因为额外的重复面值不会给“最少硬币数”带来任何新收益但会严重干扰方案计数。去重可以在输入环节就做也可以在最前面加一句coins set(coins)。7.5 当硬币面值有0或者负数这是个极端的脏数据场景但刷题群里偶尔会有人问。如果硬币面值是0循环会陷入死循环因为i - coin等于idp[i]会被自己无限更新。负数面值会让数组索引变成负数直接报错。正规题目不会给这种数据但如果你在处理真实业务数据必须在预处理阶段过滤掉coin 0的条目。7.6 内存优化的一些经验最少硬币问题用一维dp数组就够了空间复杂度 O(amount)时间 O(n * amount)。有些同学一开始习惯写二维dp[i][j]表示“前 i 种硬币凑出金额 j”这样当然对但完全背包场景下二维转一维非常自然原因在于第 i 种硬币可以无限取状态只在当前金额维度上滚动。如果你还在写二维版本强烈建议推一遍一维的等价性二维转移是dp[i][j] min(dp[i-1][j], dp[i][j-coin]1)压缩后变成dp[j] min(dp[j], dp[j-coin]1)内层正序保证dp[j-coin]是已经使用过当前硬币的最新值这一下就把重复使用的语义体现出来了。8. 从硬币问题到背包问题的统一视角到这里最少硬币、组合方案数、输出全部路径都讲完了。最后我想展开聊一下硬币问题为什么值得单独写一篇它和其他动态规划题型之间到底是什么关系。8.1 硬币问题就是完全背包问题的马甲你在很多教程里看到的完全背包模板是有N件物品每件物品重量为w[i]价值为v[i]每种物品无限量背包容量为C求最大价值。把它稍微改一下把“重量”换成“硬币面值”把“价值”改成“硬币数量”问题就变成了“装满背包最少的物品数量”。这不是巧合而是同一类状态转移在不同场景下的变体。所以你可以把硬币问题当作一个“完全背包的原型题”来记忆。一旦你看穿这层关系很多看起来花里胡哨的题都能快速归位。比如有些题目说“一个整数可以拆成几个数的和每个数可以用多次求拆分方式数”本质上就是硬币问题的换皮。只要把“硬币”换成“可使用的数集”代码都不用改。8.2 什么时候不能用硬币问题的套路硬币问题的完全背包套路有一个前提硬币数量无限且独立。如果题目改成“每种硬币只能用一次”它就变回了0-1背包问题此时内层遍历方向必须倒过来而且不能用我们前面讲的正序更新。如果题目改成“每种硬币最多使用 c[i] 次”这变成了多重背包需要拆分物品或用单调队列优化。所以拿到题目第一步不是直接套模板而是先判断物品的使用限制这是几个背包问题里最关键的分水岭。8.3 我的学习路径建议如果你还在学习阶段我的建议是这样的顺序先把暴力递归写到滚瓜烂熟然后手动模拟dp数组的更新过程亲手写一遍一维滚动数组再去刷LeetCode 322、518、377这三道经典题。刷完之后试着把“输出全部方案”的回溯逻辑补充到你的模板里。走完这一套硬币问题就算真正吃透了。别急着刷难题先把基础动作练好后面遇到再变形的背包题你会发现自己能很自然地对应到背包模型上而不是那个只会背代码的“模板选手”。结合这几年的刷题和实际写业务代码的经验我个人最大的体会是硬币问题是少数几个“能把dp思想讲明白”的代表性题目它的代码很短但背后的递推关系、遍历方向、状态设计、边界处理样样都是硬功夫值得反复咀嚼。