动态规划入门：从最少硬币到背包问题的核心原理与实战

1. 先搞清楚：动态规划到底在解决什么问题

我最早接触动态规划的时候，差点被教材上的定义劝退："动态规划是求解最优化决策过程的方法"——看完这句话，除了觉得高深，完全不知道它有什么用、什么时候该用它。后来真正搞懂，是从一个找零钱的问题开始的：假设便利店收银台里有面值为 1 元、3 元和 5 元的硬币若干枚，需要给顾客凑出 11 元，问最少用多少枚硬币。

正常人第一反应是贪心：先拿大的，11 元先拿两枚 5 元，余 1 元再拿一枚 1 元，总共 3 枚。但这个答案其实不是最优的——3 元硬币呢？5 + 3 + 3 = 11，同样 3 枚；5 + 1 + 1 + 1 + 1 + 1 + 1 = 11，要 7 枚。看起来贪心已经拿到了最优解，那换一组面值试试：硬币面值是 1、4、5 元呢？贪心的做法是 5 + 5 + 1 = 11，用了 3 枚；但 4 + 4 + 3 不行，我们没 3 元硬币，4 + 4 + 1 + 1 + 1 也更多。实际上 5 + 4 + 1 + 1 = 4 枚，5 + 5 + 1 已经是近优——“等等，4 + 4 + 4 是 12，超了；4 + 4 + 1 + 1 + 1 = 11，5 枚。看起来 5 + 5 + 1 确实 3 枚最优。”这个例子不够直观，我们换一种思路。

著名的最小硬币问题场景是：硬币面值为 1、3、5 元，凑 11 元，贪心给 2 枚 5 元 + 1 枚 1 元 = 3 枚。那凑 9 元呢？贪心：5 + 3 + 1 = 3 枚；但最优其实是 3 + 3 + 3 = 3 枚，一样。凑 8 元：贪心 5 + 3 = 2 枚，最优 5 + 3 = 2 枚。贪心和最优总是难得一致。真正经典的反例是面值 1、3、4 元凑 6 元。贪心：4 + 1 + 1 = 3 枚。最优：3 + 3 = 2 枚。看，贪心在这里就失效了——它在每个局部选择"当前面额尽可能大"的硬币，但局部最优加起来不是全局最优。这背后的原因是：贪心策略没有考虑"我选了这枚硬币之后，剩下的钱还能不能凑出最优解"。

暴力穷举倒是肯定能找到答案：把所有可能的组合都试一遍，选硬币数最少的方案。但问题是它的复杂度是指数级的——比如凑 30 元，直接炸掉。那怎么才能在"不盲目试所有组合"的情况下，既找到全局最优解，又控制住计算量？这就是动态规划的核心出发点：我们发现，凑 11 元的最少硬币数，其实可以用更小的金额推导出来——如果我先用一枚 5 元硬币，剩下要凑 6 元；先用一枚 3 元，剩下凑 8 元；先用一枚 1 元，剩下凑 10 元。那么：

f(11) = min(f(10) + 1, f(8) + 1, f(6) + 1)

而 f(10)、f(8)、f(6) 又可以用同样的方式继续拆。这就是动态规划解决问题的基本思路：把原问题拆成规模更小的子问题，先解决子问题，再用子问题的答案拼出原问题的答案。和分治法的区别在于，这些子问题之间高度重叠——f(6) 既被 f(11) 用到，又可能被 f(10) 通过 10 - 4 用到。既然重复计算，那不如把每个子问题的结果存下来，用空间换时间。

1.1 状态、转移方程、边界条件：动态规划的标配三件套

动态规划求解最优化决策过程，有几个绕不开的术语：状态、状态转移方程、边界条件/初始状态。

状态描述的是"我在求解过程中处于哪一步、手里拿着什么信息"。在最少硬币问题里，状态就是"还要凑多少元"，也就是 f(i) 的 i。在背包问题里，状态就是"已经考虑了前几个物品 + 当前背包剩余容量"。

状态转移方程描述的是"从一个状态如何走到另一个状态"，公式化地告诉计算机：当前状态的最优解，依赖于哪些更小的状态。最少硬币问题的转移方程就是上面写的 f(n) = min(f(n - 1), f(n - 3), f(n - 5)) + 1。

边界条件是递归的出口，也是递推的起点。比如 f(0) = 0，含义是"凑 0 元不需要任何硬币"。边界条件定义错了，整个 DP 表都会错，这一点我会在后面单独拿出来讲，因为它是新手最容易踩的坑。

一套完整的动态规划解法，本质上就是回答三个问题：状态怎么定义？转移方程怎么列？边界条件是什么？想清楚这三个问题，代码写起来特别快；想不清楚，看再多代码也白搭。

2. 判断一个题能不能用 DP：三大前提条件

很多人的困境是：上课听懂了，例题看明白了，一到新题就懵——完全不知道这道题该不该用动态规划。其实判断标准很固定，一道题能用动态规划解，必须同时满足三个条件：最优子结构、重叠子问题、无后效性。这三个性质缺一个，DP 都不适用。

2.1 最优子结构：大问题的最优解由子问题的最优解拼出来

"最优子结构"用大白话说就是：如果我要求原问题的最优解，那么原问题的最优解里包含的每一个子问题，必须也是对应子问题的最优解。一件很微妙的事是，像"从起点到终点最短路径"这种问题，满足最优子结构——如果你从 A 到 C 的最短路径经过了 B，那么从 A 到 B 的这段路径也必然是从 A 到 B 的最短路径，否则你可以换一段更短的 A 到 B 路径，从而得到更短的 A 到 C 路径，这就产生了矛盾。

反过来，如果不满足最优子结构，DP 就直接失效。一个典型反面例子是"最长简单路径"问题：在一个带权图里找从 A 到 B 的最长路径，且路径不能经过重复顶点。这个问题不满足最优子结构，因为从 A 到 C 的最长路径经过 B 时，A 到 B 的那一段未必是 A 到 B 的最长路径——B 可能为了 C 而"牺牲"了 A 到 B 的路径长度，以确保整条路径是简单路径且最长。如果强行套 DP 的"子问题最优拼全局最优"，算出来的东西未必是全局最优。

所以见到求"最大值、最小值、最少个数、最优方案"这类最优化问题，先别急着套 DP，先想一想：原问题的最优解能不能由规模更小的子问题的最优解直接组合出来？能，才有 DP 的入场券。

2.2 重叠子问题：为什么 DP 比暴力递归快那么多

动态规划省时间的核心就是"重叠子问题"。从斐波那契数列这个最朴素的例子看起：F(n) = F(n-1) + F(n-2)，递归展开之后是一棵巨大的二叉树，F(5) 要算 F(4) 和 F(3)，F(4) 又要算 F(3) 和 F(2)，F(3) 被算了两次，F(2) 被算了三次……随着 n 增大，重复计算量爆炸式增长，时间复杂度 O(2^n)。

但如果用一个数组把每一步的结果存下来：F(0)、F(1) 是已知的，从 F(2) 一路递推到 F(n)，每个值只算一次，时间复杂度降到了 O(n)。这就是动态规划"用空间换时间"的本质：把暴力递归中重复计算的子问题缓存起来，避免同一个子问题被反复求解。

对比之下，分治算法（比如归并排序）虽然也把问题拆成子问题，但它的子问题是互不重叠的——左半部分排序和右半部分排序互不相干，不存在"同一个子问题被多个父问题共用"的情况。这种"每个子问题只在一个父问题中出现"的特征，决定了分治不需要缓存子问题的结果，也正因如此，分治适合用递归实现，而 DP 适合用递推或记忆化搜索实现。

2.3 无后效性：一旦状态确定，未来就不回头

无后效性这个术语很容易把人吓住，但它其实就是一句话：一个状态一旦确定，之后怎么决策，只取决于这个状态本身是怎么样的，不取决于它是通过什么路径到达这个状态的。换句话说，历史不影响未来，未来只由当前状态决定。

还是用找零钱的例子。状态 f(6) 代表"凑 6 元最少需要多少个硬币"，这个状态值是多少就是多少，跟它是通过"先拿 5 元再拿 1 元"凑出来的，还是通过"拿两个 3 元"凑出来的，完全没关系。后续计算 f(11) 的时候，只需要知道 f(6) = 2，不需要知道这个 2 是怎么来的。正是因为这种无后效性，DP 才能放心地只存"最优结果"，而不用存"得到这个结果的完整路径"。

什么情况下会破坏无后效性？只要决策函数需要考虑"之前做了什么路径"，DP 就难办了。比如“带限制的最短路径”：要求从 A 到 C 必须经过 B，那状态就得额外记录"是否已经经过 B"这个历史信息。强行用普通 DP 会算出错误答案——所以这类题必须额外增加状态维度，用状态来"记住"历史的关键信息，从而把无后效性重新找回来。

3. 经典例题实操一：最少硬币问题的三种写法进化史

理论说了一堆，不来点实操总觉得不落地。最少硬币问题特别适合用来展示从暴力到 DP 的完整演化过程，我们仔细看一遍。

问题定义：给定一个硬币面值数组 coins = [1, 3, 5]，每种硬币无限量，问凑出金额 n 最少需要多少个硬币？如果凑不出来返回 -1。

3.1 暴力递归：能解，但指数级爆炸

暴力递归的思路非常直接：要凑 n 元，第一枚硬币我可以尝试 1、3、5，于是存在三种选择。对每个选择，剩下的金额又可以用同样的方式继续凑：

def coin_change_brute(coins, n): if n == 0: return 0 if n < 0: return float('inf') result = float('inf') for c in coins: result = min(result, 1 + coin_change_brute(coins, n - c)) return result

这个解法唯一能保证的是正确性。它的时间复杂度是 O(branch^n)，branch 是硬币种类数，n 是金额，20 元的输入就能跑得怀疑人生。原因就是我们前面说的重叠子问题：coin_change_brute(5) 会在计算 coin_change_brute(10) 和 coin_change_brute(8) 时各被调用若干次。

3.2 记忆化搜索：自顶向下 + 缓存，先告别超时

既然是重复算同一个子问题，用字典把算过的结果记下来就行。递归加了缓存之后，每个金额只需要真正计算一次：

from functools import lru_cache def coin_change_memo(coins, n): @lru_cache(None) def dp(amount): if amount == 0: return 0 if amount < 0: return float('inf') best = float('inf') for c in coins: best = min(best, 1 + dp(amount - c)) return best return dp(n)

记忆化搜索的代码和暴力递归几乎一样，只是加了一层缓存，但时间复杂度从 O(branch^n) 降到 O(n * branch)。这种"自顶向下 + 缓存"的写法，本质就是动态规划，只不过实现方式还保留着递归的外壳。实际刷题时如果一时间想不清递推顺序，先写记忆化搜索是一个很稳妥的中间方案——正确性几乎和白板递归一样直观，性能又够用。

3.3 自底向上的递推 DP：正式写法

递推 DP 的思路反过来：既然 f(n) 依赖于 f(n-1)、f(n-3)、f(n-5)，那我干脆从 0 开始把从小到大的 f 值全部算出来，填进一个数组里：

def coin_change_dp(coins, n): dp = [float('inf')] * (n + 1) dp[0] = 0 for amount in range(1, n + 1): for c in coins: if amount - c >= 0: dp[amount] = min(dp[amount], dp[amount - c] + 1) return dp[n] if dp[n] != float('inf') else -1

时间复杂度和记忆化搜索一样是 O(n * branch)，空间复杂度为 O(n)。这里 dp[i] 的含义是"凑 i 元所需的最小硬币数"，这就是状态；等式中 dp[amount] = min(...) 就是状态转移方程；dp[0] = 0 就是边界条件。

一个小提醒：递推的顺序很关键。最少硬币问题是"从小的金额往大的金额递推"，因为大金额依赖于小金额。但后面要讲的背包问题里，遍历顺序会直接影响正确性——同一种遍历方式，在完全背包和 01 背包中的含义完全不同，这是经典考点，下一章单独说。

4. 经典例题实操二：01背包问题与滚动数组优化

01背包是动态规划中出镜率最高的题目，没有之一。它的标准描述是：有一个承重为 W 的背包，有 n 件物品，每件物品重量为 wt[i]，价值为 val[i]，每件物品只能选择拿或不拿，问在不超重的前提下，背包里能装下的最大总价值是多少。

4.1 为什么不能用贪心：价值重量比陷阱

很多新手第一反应是"按性价比排序，优先装性价比高的"。这个做法在部分测试用例下是对的，但有反例：背包承重 10，物品 A 重 6 价值 30（性价比 5），物品 B 重 5 价值 20（性价比 4），物品 C 重 5 价值 20（性价比 4）。按性价比贪心只能装一个 A，总价值 30；但装 B + C，总价值 40，明显更高。贪心失败的原因在于背包是一个"0/1决策"问题——你没法装"0.8 个 A"，而贪心的连续性假设在这里不成立。

4.2 状态定义与二维 DP 表

01背包的状态需要两个维度：已经考虑了前多少件物品、当前背包剩余容量。定义 dp[i][j] 表示"从前 i 件物品中挑选，放入容量为 j 的背包中，能获得的最大价值"。dp[i][j] 究竟是什么？就是从第 1 件到第 i 件中选一些放入容量为 j 的背包的最大价值。

对于第 i 件物品，有两种决策：

• 不拿：问题变成"从前 i-1 件里挑，容量还是 j"，即 dp[i-1][j]；
• 拿（前提是 wt[i] <= j）：问题变成"前 i-1 件里挑，放进容量 j - wt[i] 的背包，然后再加上第 i 件物品的价值"，即 dp[i-1][j - wt[i]] + val[i]。

取两者的最大值，就是状态转移方程：

def knapsack_01(wt, val, W): n = len(wt) dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, W + 1): if j < wt[i - 1]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]) return dp[n][W]

这里的 dp 表是一个 (n+1) x (W+1) 的二维矩阵。仔细看转移方程会发现一件事：dp[i][j] 永远只依赖 dp[i-1][...] ——也就是依赖上一行的结果。这意味着二维表其实有很多历史信息是算完之后就再也用不上的，这为空间优化提供了空间。

4.3 一维滚动数组与遍历顺序的玄机

既然 dp[i][j] 只依赖上一行的值，那我们完全可以用一维数组滚动更新，把空间从 O(n * W) 压到 O(W)：

def knapsack_01_optimized(wt, val, W): n = len(wt) dp = [0] * (W + 1) for i in range(n): for j in range(W, wt[i] - 1, -1): dp[j] = max(dp[j], dp[j - wt[i]] + val[i]) return dp[W]

注意这里的循环顺序：内层容量遍历是从大到小。为什么不能从小到大？因为一维数组里 dp[j - wt[i]] 如果在本轮遍历中被提前更新了，那就等于把"第 i 件物品"用了两次，这就变成了完全背包的逻辑。从大到小遍历，能保证 dp[j - wt[i]] 在更新 dp[j] 时，仍然是"上一轮（只考虑前 i-1 件物品）"的结果。我第一次写成从小到大，查了半天 bug 才明白是循环顺序的问题——这个坑值得单独标出来。

保持一维写法不变，只把内层循环改成从小到大，就是从可重复取物品的"完全背包"解法。很多资料用两句话把 01背包和完全背包的区别带过："01背包内层倒序，完全背包内层正序"。我当时看了就在想为什么，现在总结起来其实就是三个字：防复用。

4.4 边界条件与初始化：dp[0] 的含义一错全错

背包问题的 dp[0]（容量为 0）初始化为 0，表示装不进任何东西时价值为 0；最少硬币问题的 dp[0] = 0，表示金额为 0 时一枚硬币都不用。如果题目改成"恰好装满背包"而不是"最多能装多少"，dp 数组初始化的方式就要变——dp[0] 仍然是 0，但其他容量要初始化为负无穷，表示"装不满的情况是非法的"，然后从这些非法状态转移出来的状态也都是非法的。

这是很多教程不会刻意强调的细节，但在笔试里非常常见。"最多装多少"和"恰好装满"是两种不同语义的 DP，初始化方案天差地别。我建议做题时先明确题目的真实要求，再决定初始化边界，而不是默认套用模板。

5. 动态规划和分治、贪心、暴力穷举、回溯的对比

很多初学者把动态规划和贪心、分治混在一起，因为它们都涉及"把大问题拆成小问题"。这里必须理清楚：它们的拆解逻辑完全不同。

5.1 分治 vs DP：子问题是否独立是分水岭

分治和 DP 最容易混淆，因为两者都"递归地解决子问题"。分治的代表是归并排序：把数组从中间一分为二，左半边排序和右半边排序互不干扰，各自的结果合并起来就是最终答案。左半边的排序结果不会用到右半边的结果，两个子问题完全独立，不存在"重复计算同一个子问题"的情况。

DP 则相反，只有子问题之间高度重叠，"缓存子问题结果"这件事才划算。所以分治和 DP 的核心分界线不是"有没有递归"，而是子问题是否独立、是否重叠。如果一个题满足最优子结构但不满足重叠子问题，用 DP 虽然不会错，但并不会有性能红利——它本质上退化成了分治。

5.2 贪心 vs DP：局部最优 vs 全局最优

贪心和 DP 都是最优化算法，但看待问题的方式完全不同。贪心每一步都做出在当前看来最好的选择，希望通过一系列局部最优决策达成全局最优，它不会回头重新考虑之前的决策。DP 则把每一步的所有可行选择都纳入考虑，从所有子问题的最优解中选出全局最优，它不会为了省计算而跳过某些状态。

前面的最小硬币例子已经说明：当局部最优不等于全局最优时，贪心会给出错误的答案，但 DP 依然正确。反过来说，如果一道题满足贪心选择性质，贪心算法的实现往往更简单、更快——比如找零钱问题在美元面额体系下（1, 5, 10, 25），贪心恰好总是最优；只有面额不规律时，才需要 DP 兜底。所以我做题的顺序是：先分析能不能贪心，不能才上 DP。很多人一上来就写 DP，反而把自己绕进复杂度里。

5.3 暴力穷举 / 回溯 vs DP：记忆化是唯一的区别

回溯算法在搜"所有解"或者"需要枚举路径"的问题时是主力，比如八皇后、排列组合、迷宫求解。DP 和它的最大区别是：回溯会重复探索大量相同的子问题，而 DP 通过备忘录或 DP 表把这些子问题的结果存起来，避免重复。

有一个很好的角度理解这件事：DP 穷举的是状态空间，而回溯穷举的是方案空间。状态空间往往比方案空间小几个数量级。斐波那契数列用回溯式的递归展开是 2^n 个节点，用 DP 只遍历 n 个状态，差别就在这。

6. 实战刷题中的高频坑：条件与边界

最后分享几个我实际写 DP 踩过多次的坑，每一个都对应真实的调试经历。

6.1 状态定义错了，后面全白做

状态定义是 DP 的第一颗扣子，这颗扣子扣错，后面写出花来答案都不对。一个经验是：在定义状态前，先把"题目在问什么"翻译成一句话——"在 xxx 条件下，求 xxx 的最值"。然后让状态包含"条件中随规模变化的所有必要信息"。比如二维背包问题，多了"体积"和"重量"两个约束，状态就必须是三维 dp[i][j][k]；如果你强行用二维存，信息就不够，转移自然会错。

6.2 初始化和循环方向的组合坑

初始化表达的是"问题的最简单版本"，循环方向体现的是"依赖关系"。两者必须和状态定义保持一致。经典组合就是 01 背包的一维压缩：当容量需要从大到小遍历，而你不小心写反，结果就会从"每件物品用一次"悄悄变成"每件物品无限用"。这类 bug 在答案恰好恰好一致时不明显，一旦用例只有部分正确，排查难度极高。

我自己的定位习惯是：写完 DP 后，手动把一个小规模例子（比如 n=3, W=6）从头到尾模拟一遍表格的填充过程，亲眼看看每个格子依赖的值是不是上一轮的结果。这个过程虽然原始，但能最快发现循环方向和初始化的问题。

6.3 哪些场景应该直接放弃 DP

不是所有"最优化问题"都能用 DP 解决。除了前面提到的最长简单路径之外，带负权环的最短路、需要输出完整路径且路径量巨大的问题、子问题无法无后效化的问题，DP 都不是好选项——要么正确性不保证，要么时间空间双炸。现实中遇到不熟悉的题，我一般先暴力递归写一遍，得到正确答案，再尝试用记忆化/DP 优化，这个流程既保证正确性，又能自然地检验状态定义是否合理。

7. 一个建议：刷动态规划题的正确学习路径

如果让我给刚接触 DP 的人一个学习路径的建议，我会推荐"三步走"：先暴力递归，再记忆化搜索，最后递推 DP。很多人嫌弃第一步暴力递归"太傻"，直接跳着学递推表格，结果遇到新题时，既不知道状态怎么定义，也不知道转移怎么列。

暴力递归的价值是帮你想清楚"问题的自相似结构"——它逼着你回答：原问题怎么拆成子问题？拆到什么时候停止？这个递归结构一旦写对，加一个缓存就是记忆化搜索，再把递归改成从底向上的填充就是递推 DP。三种写法背后是同一个状态转移方程，性能却从指数级逐步优化到多项式级，这就是"先用结果正确性验证思路，再用数据结构做优化"的工程方法论。这种思路不只是 DP 通用，放在整个算法学习里都非常受用。

我在实际解题的时候，还有一个习惯：把每道 DP 题的"状态定义 + 边界条件 + 转移方程"单独写进笔记，而不只是贴一段通过测试的代码。因为代码会过时，但那个"为什么这样定义状态"的思考链路不会——等刷过 30 道题再回头看，你会发现大部分 DP 题都长得差不多，无非就是状态多一维少一维、转移方程是取 max 还是取 min、初始化是 0 还是正负无穷的区别。

动态规划这个知识点，刚接触时总觉得玄学，但只要你把"重叠子问题、最优子结构、无后效性"三个前提嚼碎，把暴力递归、记忆化搜索、递推 DP 三个层次打通，再配上 01 背包、最少硬币这类经典题目反复练习，它就会从"玄学"变成"套路"，而且是很实用、很通用的套路——至少我后来在处理资源分配、路径规划、文本对齐这类工程问题时，DP 依然是我第一个想到的解法。