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 115 枚。看起来 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 表是一个 (n1) x (W1) 的二维矩阵。仔细看转移方程会发现一件事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 后手动把一个小规模例子比如 n3, W6从头到尾模拟一遍表格的填充过程亲眼看看每个格子依赖的值是不是上一轮的结果。这个过程虽然原始但能最快发现循环方向和初始化的问题。6.3 哪些场景应该直接放弃 DP不是所有最优化问题都能用 DP 解决。除了前面提到的最长简单路径之外带负权环的最短路、需要输出完整路径且路径量巨大的问题、子问题无法无后效化的问题DP 都不是好选项——要么正确性不保证要么时间空间双炸。现实中遇到不熟悉的题我一般先暴力递归写一遍得到正确答案再尝试用记忆化/DP 优化这个流程既保证正确性又能自然地检验状态定义是否合理。7. 一个建议刷动态规划题的正确学习路径如果让我给刚接触 DP 的人一个学习路径的建议我会推荐三步走先暴力递归再记忆化搜索最后递推 DP。很多人嫌弃第一步暴力递归太傻直接跳着学递推表格结果遇到新题时既不知道状态怎么定义也不知道转移怎么列。暴力递归的价值是帮你想清楚问题的自相似结构——它逼着你回答原问题怎么拆成子问题拆到什么时候停止这个递归结构一旦写对加一个缓存就是记忆化搜索再把递归改成从底向上的填充就是递推 DP。三种写法背后是同一个状态转移方程性能却从指数级逐步优化到多项式级这就是先用结果正确性验证思路再用数据结构做优化的工程方法论。这种思路不只是 DP 通用放在整个算法学习里都非常受用。我在实际解题的时候还有一个习惯把每道 DP 题的状态定义 边界条件 转移方程单独写进笔记而不只是贴一段通过测试的代码。因为代码会过时但那个为什么这样定义状态的思考链路不会——等刷过 30 道题再回头看你会发现大部分 DP 题都长得差不多无非就是状态多一维少一维、转移方程是取 max 还是取 min、初始化是 0 还是正负无穷的区别。动态规划这个知识点刚接触时总觉得玄学但只要你把重叠子问题、最优子结构、无后效性三个前提嚼碎把暴力递归、记忆化搜索、递推 DP 三个层次打通再配上 01 背包、最少硬币这类经典题目反复练习它就会从玄学变成套路而且是很实用、很通用的套路——至少我后来在处理资源分配、路径规划、文本对齐这类工程问题时DP 依然是我第一个想到的解法。