企业官网建设流程全解析

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，从头到尾更新：

• i=1: dp[1] = min(inf, dp[0]+1) = 1
• i=2: dp[2] = min(inf, dp[1]+1) = 2
• i=3: dp[3] = min(inf, dp[2]+1) = 3
• ... 一直到 dp[8] = 8

此时全部用1元硬币，得到一种可行方案。

第二轮，coin = 3：

• i=3: dp[3] = min(3, dp[0]+1) = 1
• i=4: dp[4] = min(4, dp[1]+1) = 2
• i=5: dp[5] = min(5, dp[2]+1) = 3（这里 dp[2]=2 是上一轮用1元硬币的结果）
• i=6: dp[6] = min(6, dp[3]+1) = 2（dp[3] 刚刚被更新为1，所以可以用3+3凑出6）
• i=7: dp[7] = min(7, dp[4]+1) = 3
• i=8: dp[8] = min(8, dp[5]+1) = 4

第三轮，coin = 5：

• i=5: dp[5] = min(3, dp[0]+1) = 1
• i=6: dp[6] = min(2, dp[1]+1) = 2
• i=7: dp[7] = min(3, dp[2]+1) = 3
• i=8: 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]
• coin=1: 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}
• coin=2: dp[2]+=dp[0]=2, dp[3]+=dp[1]=2
• 最终 dp[3]=2，方案是 {1,1,1} 和 {1,2}

外层金额、内层硬币（排列数）：

• i=1: dp[1] += dp[0] = 1（用1），dp[1] 无法用2
• i=2: dp[2] += dp[1] = 1（用1），dp[2] += dp[0] = 2（用2）
• i=3: dp[3] += dp[2] = 2（用1），dp[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] 、目标 6，dp[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等于i，dp[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思想讲明白”的代表性题目，它的代码很短，但背后的递推关系、遍历方向、状态设计、边界处理，样样都是硬功夫，值得反复咀嚼。