动态规划是我这几年刷题和工作里最常打交道的一类算法也是很多人从入门到放弃的分水岭。一开始接触的时候我也觉得它玄乎什么“状态转移”“最优子结构”听起来像天书后来做多了才明白动态规划说白了就是把大问题拆成小问题先算小问题再一步步推到大问题整个思考路径其实非常朴素。这篇文章我想把我自己从理解到熟练这套算法的完整过程写一遍包括三大基本要素、标准解题步骤、几道高频例题的完整代码以及在时间复杂度和空间复杂度上的优化手段最后再整理一下我踩过的坑。不管你是正在准备面试还是工作中遇到路径规划、资源分配、成本优化这类问题这篇文章应该都能帮你把动态规划这层窗户纸捅破。1. 动态规划到底在解决什么问题——三大基本要素拆解先聊一个最基础的问题什么样的问题适合用动态规划什么样的问题不适合。很多人一上来就背模板结果遇到新题完全套不上根源就在于没理解动态规划的适用条件。我习惯用一句话概括如果一个问题可以拆成若干个相互关联的子问题而且这些子问题会被反复计算那它大概率就是动态规划的菜。1.1 最优子结构大问题拆小问题的前提“最优子结构”这个术语听起来正式其实意思特别直白大问题的最优解可以由子问题的最优解拼出来。我举个生活化的例子。假设你要从公司回家中间必须经过地铁换乘站如果你从公司到换乘站选择了最短路线从换乘站到家也选择了最短路线那么整条路线就是最短的。这时候我们说这个问题具备最优子结构——因为“全局最优”包含了“局部最优”。反过来如果一个问题不具备这种性质动态规划就不好使了。比如你要规划一条既要经过景点A又要经过景点B的路线A和B之间的顺序会互相影响那么局部最优拼起来就不一定是全局最优这种情况更倾向于用搜索或者其它方法。放在动态规划里最优子结构直接决定了我们能不能写状态转移方程如果没有最优子结构你从子问题那里拿到的最优结果根本不敢用那整个递推就失去了依据。1.2 状态转移方程整个算法的灵魂如果说最优子结构是动态规划成立的“前提”那状态转移方程就是动态规划的“发动机”。所谓状态转移方程就是描述当前状态如何从前面的状态推导出来的数学表达式。我经常用一个比喻状态转移方程就像菜谱里的“下一步”。你知道当前锅里有什么当前状态也知道上一步发生了什么前一个状态按菜谱操作就能得到下一道菜下一个状态。拿经典的爬楼梯问题来说你每次可以爬1级或2级台阶问爬到第n级有多少种方法。这里的状态就是dp[i]表示爬到第 i 级台阶的方法数。怎么到第 i 级只有两种可能从第 i-1 级迈1步或者从第 i-2 级迈2步。所以状态转移方程就是dp[i] dp[i-1] dp[i-2]这个方程一写出来整个问题就变成了一个简单的循环。很多初学者卡在动态规划上不是不会写循环而是写不出这个方程。我在后面第2部分会专门讲怎么写状态转移方程这里先记住一个结论状态转移方程想的是“最后一步是怎么走的”而不是“第一步怎么走”。1.3 重叠子问题递归为什么会超时第三个要素是重叠子问题。它指的是在拆解大问题的过程中同一个子问题会被反复计算很多次。还是说爬楼梯。如果你用朴素的递归去算dp[50]计算过程会像一棵疯狂膨胀的树。dp[50]要算dp[49]和dp[48]而dp[49]又要算dp[48]和dp[47]其中dp[48]被重复算了两次。越往下层重复计算越严重整个计算量是指数级的。动态规划的核心价值就在这里把已经算过的子问题结果保存下来下次用到时直接查表而不是重新递归计算。这也是为什么动态规划通常比朴素的递归快几个数量级。我用一个简单的对比来看同样是计算dp[40]纯递归可能要做上亿次函数调用而动态规划只需要40次循环。差距就是这么恐怖。需要强调的是这三个要素不是孤立的最优子结构决定了问题能不能拆重叠子问题决定了拆了之后值不值得用动态规划状态转移方程则是把“拆”和“复用”串联起来的那根线。2. 完整解题步骤——从读题到AC的五个环节很多人在拿到一道动态规划题的时候大脑一片空白不知道该从哪里下手。我自己也经历过这个阶段。后来我总结出一套固定的解题流程每一步该干什么都写清楚。按这个流程走即使不能保证一次AC至少不会毫无头绪。2.1 定义状态dp数组里每个格子的含义第一步永远是定义状态也就是回答一个问题这个dp数组到底存的是什么这里有一个很关键的习惯不要用dp[i]这种模糊的写法敷衍自己要在一开始就用一句话把状态说清楚。比如dp[i]表示“前 i 天能获得的最大利润”dp[i][j]表示“考虑前 i 个物品、背包容量为 j 时能装下的最大价值”dp[i][j]表示“从字符串 s 的前 i 个字符匹配到字符串 t 的前 j 个字符所需的最小编辑距离”大家会发现状态定义清楚了题目思路就清晰了一半。状态定义得越具体后面写转移方程就越不容易跑偏。我这几年做动态规划题最大的体会是状态的定义要以“能直接回答题目问题”为目标。题目问什么状态就定义成什么。如果题目问“最少需要几枚硬币凑出X元”那dp[amount]就定义成“凑出 amount 元所需的最少硬币数”不要绕弯子。2.2 写状态转移方程先想“最后一步”定义好状态之后接下来就是写状态转移方程。这一步我会刻意训练自己一个问题如果我知道了所有更小的子问题的答案我能不能通过某种操作得到当前问题的答案以最少硬币问题为例有面值为[1, 2, 5]的硬币问凑出amount 11元最少需要几枚硬币。假设我已经知道了dp[10]、dp[9]、dp[6]也就是凑出10、9、6元所需的最少硬币数那么凑11元只有三种可能先凑10元再拿1枚1元硬币先凑9元再拿1枚2元硬币先凑6元再拿1枚5元硬币取这三者中的最小值加1枚当前硬币就是dp[11]dp[11] min(dp[10], dp[9], dp[6]) 1把具体数字换成通用形式dp[i] min(dp[i - coin] for coin in coins if i coin) 1大家注意我在推转移方程的时候想的是“最后一步如果取一枚面值为 coin 的硬币那前面就必须凑出 i-coin 元”这就是倒着思考。这个思维方式和正向贪心完全不同也是动态规划最反直觉但又最核心的地方。2.3 初始化与遍历顺序最容易翻车的两个细节状态转移方程写出来以后还有两个细节如果不注意代码写出来就会直接报错或者得出错误结果。第一是初始化。dp数组的某些位置没有前置状态必须手动给值。还是用最少硬币问题举例dp[0]表示凑出0元需要的硬币数答案当然是0。如果这个值不初始化好后面所有递推都会乱掉。再比如爬楼梯问题通常初始化dp[1] 1和dp[2] 2。第二是遍历顺序。这一步很重要但经常被忽略你需要保证计算dp[i]的时候它依赖的所有状态都已经计算过了。所以遍历顺序本质上是由状态转移方程决定的不是拍脑袋定的。注意如果你用的是正向递推从1到n计算那么方程里依赖的dp[i-1]、dp[i-2]等必须已经在前面算好了如果你用的是记忆化搜索自顶向下后面会讲则依赖关系由递归天然保证不需要手动考虑顺序。2.4 空间优化滚动数组是怎么来的把上面三步做完一道题基本上已经能写出能跑的版本了。但有些题目对空间有额外要求或者数据量很大导致二维数组放不下这时候就需要做空间优化。空间优化最常用的手段就是滚动数组。原理特别简单如果状态转移方程里dp[i]只依赖dp[i-1]和dp[i-2]那前面算完的dp[i-3]、dp[i-4]就再也不会被用到了留着纯属浪费空间。所以我们只用两三个变量循环滚动不需要保留整个数组。爬楼梯问题用滚动数组优化后大概长这样def climb_stairs(n: int) - int: if n 2: return n prev2, prev1 1, 2 # dp[1], dp[2] for _ in range(3, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1这样一来空间复杂度从O(n)降到了O(1)在大规模数据下优势非常明显。3. 经典例题详解——从入门到实战的四个案例光讲理论不写代码等于白学。这一部分我选了四道有代表性的题目难度从入门到进阶每道题都会给完整代码和关键注释。这四道题覆盖了最基础的线性DP、二维背包DP以及实际工作中会遇到的路径规划和切割优化问题。3.1 最少硬币问题入门必写的“凑零钱”这道题可以说是动态规划的“hello world”也是面试里出现频率极高的题目。题目描述给定不同面额的硬币coins和一个总金额amount编写一个函数计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。思路定义dp[i]表示凑出金额 i 所需的最少硬币数。初始化dp[0] 0其它位置初始化为一个很大的数比如float(inf)表示暂时无法凑出。然后从1到amount遍历每个金额对每种硬币尝试更新。def coin_change(coins: list[int], amount: int) - int: dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i coin: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这里有一个细节值得关注内层循环是遍历硬币而外层是从小到大遍历金额。为什么外层不能是硬币、内层是金额这个问题我放到后面“01背包”部分展开因为不同遍历顺序在背包类问题里结果完全不同。复杂度分析时间复杂度O(amount * len(coins))空间复杂度O(amount)。这个复杂度在 amount 不是特别大的情况下完全够用。3.2 01背包问题经典中的经典01背包是动态规划里最经典的模型之一理解了它很多变种题都能触类旁通。题目描述有N件物品和一个容量为V的背包。第i件物品的重量为w[i]价值为v[i]每件物品只能用一次要么装入背包要么不装。求解将哪些物品装入背包可使价值总和最大。二维DP思路定义dp[i][j]表示“只考虑前 i 件物品在背包容量为 j 的情况下能获得的最大价值”。状态转移分两种情况不放第 i 件物品dp[i][j] dp[i-1][j]放第 i 件物品前提是j w[i]dp[i][j] dp[i-1][j-w[i]] v[i]综合起来def knapsack_2d(n: int, capacity: int, w: list[int], v: list[int]) - int: dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, capacity 1): dp[i][j] dp[i - 1][j] # 不装第 i 件 if j w[i - 1]: dp[i][j] max(dp[i][j], dp[i - 1][j - w[i - 1]] v[i - 1]) return dp[n][capacity]这里数组下标按0开始所以第 i 件物品对应w[i-1]和v[i-1]初学者很容易在这里搞混。一维滚动优化上面二维数组的空间复杂度是O(N*V)当 N 和 V 都很大的时候可能内存吃紧。观察转移方程可以发现dp[i][j]只依赖dp[i-1][...]那一行跟更早的行无关所以可以压缩成一维数组。def knapsack_1d(n: int, capacity: int, w: list[int], v: list[int]) - int: dp [0] * (capacity 1) for i in range(1, n 1): for j in range(capacity, w[i - 1] - 1, -1): dp[j] max(dp[j], dp[j - w[i - 1]] v[i - 1]) return dp[capacity]注意这里内层循环必须倒着遍历。为什么因为一维数组dp[j]在更新时如果正着遍历那dp[j - w[i-1]]可能已经被当前物品更新过了相当于同一件物品被用了多次这就变成了完全背包问题。倒着遍历可以确保用到的dp[j - w[i-1]]还停留在“上一轮”的值从而保证每件物品只选一次。提示如果你忘了该正序还是倒序就想想“01背包只能选一次”这句话。正序遍历会让一件物品被重复选择所以必须倒序如果题目改成“每件物品可以选无限次”完全背包才用正序遍历。3.3 实战延伸一车辆动态规划问题的简化模型现实中很多路径规划问题本质上也是动态规划。我这里用“车辆从起点到终点的最短行驶时间”来做一个示意图只考虑两个关键因素途经的节点和节点之间的耗时。假设从A点出发要经过若干个中间节点到达终点E每个节点之间有固定的通行耗时。定义dp[i]表示从起点出发到达节点 i 的最短时间那么状态转移可以写成def shortest_time(n: int, edges: list[tuple[int, int, int]]) - int: # edges 里的元素是 (u, v, time)表示从 u 到 v 需要 time 时间 # 这里默认节点0是起点节点 n-1 是终点 INF float(inf) dp [INF] * n dp[0] 0 # 按拓扑顺序或者简单迭代更新 for _ in range(n - 1): updated False for u, v, t in edges: if dp[u] ! INF and dp[u] t dp[v]: dp[v] dp[u] t updated True if not updated: break return dp[n - 1] if dp[n - 1] ! INF else -1这段代码其实已经有点贝尔曼-福特算法的味道了。真实场景中车辆动态规划还会涉及时间窗口、载重约束、多车协同等问题模型会复杂很多但核心思想都是一样的把整个决策过程拆成一个个子问题每个子问题只依赖前一个阶段的状态。理解了这个简化模型再去看那些复杂的调度算法会轻松很多。3.4 实战延伸二线材切割优化再来看一个工程上特别常见的场景线材切割优化。给定一根长度为L的原材料以及多种目标长度的订单每种长度都有对应售价问如何切割能让总收益最大。这个问题本质上就是完全背包的变体原材料的长度 L 是背包容量每种切割长度是物品切割后得到的售价是物品价值而且同一种切割长度可以用多次。def maximize_profit(length: int, cut_lengths: list[int], prices: list[int]) - int: # 长度需要连续所以这里把不同切割长度和价格对应起来 dp [0] * (length 1) for i in range(1, length 1): for j, cut in enumerate(cut_lengths): if i cut: dp[i] max(dp[i], dp[i - cut] prices[j]) return dp[length]这里的dp[i]表示长度为 i 的原材料能获得的最大收益。切割长度可以重复使用所以内层循环正序遍历——回想一下上面01背包里说的正序遍历恰好对应“可以重复选”的情况。这种模型在钢材、木材、线缆行业非常实用。我甚至见过有人把公司的排产问题简化成这个模型来算虽然实际生产还有损耗、库存等约束但作为第一版毛估结果已经很有参考价值了。4. 算法优化技巧——从能跑到跑得快一道动态规划题能AC之后下一步要考虑的就是能不能进一步优化。尤其在大厂面试里给出正确解只是及格线能分析出优化空间才是加分项。这一部分我挑了几个最常用的优化方向。4.1 时间优化状态压缩与斜率优化时间优化最直接的手段是状态压缩。有些DP的状态本身是集合比如“已访问过哪些城市的集合”这时候可以用二进制位来表示集合把状态从一个复杂的数据结构压成一个整数。典型例子是旅行商问题TSP的DP解法定义dp[S][v]表示“已经访问过的城市集合为S当前位于城市v”的最短路径长度。S就是一个整数的二进制位第 k 位为1表示第 k 个城市已经访问过。这种状态压缩可以把状态数从阶乘级降到O(2^n * n)虽然看起来还是很大但已经能处理 n20 左右的规模了。另一种时间优化是斜率优化适用于形如dp[i] min(dp[j] cost(j, i))的一些特殊DP。如果 cost 函数满足一定的斜率性质可以把朴素的O(n^2)优化到O(n)或O(n log n)。但斜率优化的推导比较绕面试里考得不多我建议先把前两种优化吃透再碰它。还有一种是单调队列优化它适用于dp[i]的转移范围和固定窗口有关的情况。比如滑动窗口类DP可以用单调队列把内层循环从O(k)降到O(1)。我在实际刷题中用它解决过“限制区间长度内的最大连续子段和”等问题效果显著。4.2 空间优化从二维到一维再到常数空间优化的核心思想就一句话能省则省尽早释放不再使用的数据。前面01背包已经演示了从二维数组到一维数组的优化。这里再补充一个更小的优化在爬楼梯问题里不仅不需要二维数组连一维数组都不需要只用两个变量就够因为状态只依赖前两个值。如果在实际项目里做算法移植空间优化往往比时间优化更迫切。因为嵌入式环境内存有限一个很大的二维数组可能直接让系统崩溃。我在嵌入式场景里做过类似的事情把原本O(n^2)的DP表压缩成两行滚动数组内存占用直接下降几十倍而且性能完全不受影响。这也是为什么热词列表里会出现“linux嵌入式驱动开发、系统裁剪优化”这类词——算法层面的空间优化跟系统层面的裁剪异曲同工。4.3 优雅的替代方案记忆化搜索严格来说记忆化搜索不是优化手段而是一种等价的实现方式但它在很多场景下比迭代写法更好写、更好调试所以我把它也归到优化这一小节。记忆化搜索的思路是保留递归的天然直觉但把每次递归的结果缓存起来避免重复计算。还是拿爬楼梯举例def climb_stairs_memo(n: int) - int: from functools import lru_cache lru_cache(None) def dfs(k: int) - int: if k 2: return k return dfs(k - 1) dfs(k - 2) return dfs(n)这个写法的好处是思考成本低代码结构跟题目描述几乎一致。尤其适合那种状态转移方向不明显、但递归关系很自然的问题。缺点是递归有函数调用开销而且在 Python 里如果递归深度超过1000会报错所以n特别大的时候还是老老实实写循环比较好。我在实际做题时有一个经验参考如果题目数据范围比较小比如n 1000记忆化搜索是我首选因为它不易出错如果数据范围很大那就直接上迭代版本避免递归坑。5. 动态规划避坑指南——常见问题与排查实录动态规划的代码通常不长但是写错的地方往往非常隐蔽有时候连测出来的结果都是“大部分用例通过、个别用例失败”特别折磨人。这一部分把我踩过的坑和排查经验整理出来希望能帮大家减少浪费在debug上的时间。5.1 初始化错误答案全错的根源初始化错误是动态规划里最常见的错误没有之一。我见过不少人在dp[0] 0还是dp[0] 1之间纠结或者干脆漏初始化结果整个递推从第一步就开始错。这里给大家一个通用参考初始化其实就是回答子问题的“基准情况”。问自己几个问题当我的参数取到最小合法值的时候答案应该是什么比如最少硬币问题里凑0元需要0枚硬币所以dp[0] 0如果是问方案数凑0元的方案是“什么都不选”这一种所以dp[0] 1。还有一种常见的初始化错误是把dp数组初始化为0但问题的答案可能本身就是0比如背包容量为0时最大价值为0这就导致你分不清这个0是“初始化占位”还是“算出来的正确结果”。我习惯把不确定的位置初始化为float(-inf)或float(inf)这样能明显区分未计算和已计算。5.2 数组下标问题Python也要重视细节Python的列表不会越界报错这其实是一把双刃剑。Python帮你做了边界检查但如果你用了dp[i - coin]而i - coin是负数代码会直接抛出IndexError或者更隐蔽地如果你在循环里没有判断i coin结果会非常诡异。我推荐的写法是在访问任何dp下标之前先确认下标是非负的并且没有超出数组长度。具体到硬币问题里就是if i coin: dp[i] min(dp[i], dp[i - coin] 1)5.3 状态转移方程中的“漏情况”这是最头痛的一种bug因为代码语法完全正确但答案就是不对。常见的原因有两个一是遗漏了一些转移路径。比如有些问题可以从多个前驱状态到达当前状态你只写了其中一条或两条漏了第三条。解决的办法是把状态转移关系在纸上全部列出来对照题目条件逐一确认不要光盯着代码看。二是没有考虑特殊情况比如负权边或者不可达状态。在最短路径或最小代价类DP里初始化成float(inf)后如果后续转移出现dp[u] w而dp[u]还是inf那么inf w会溢出吗在Python里不会会得到一个很大的浮点数但这个结果参与min比较时可能会导致错误。所以更稳妥的写法是判断dp[u] ! float(inf)再做转移。5.4 常见问题速查表症状可能原因排查方式答案整体偏大初始化用了很大的数或初始化错误打印前几项dp值和手算结果对比答案整体偏小初始化用了0但正确初始值应为0之外的值检查基准情况的定义部分用例通过少数超时时间复杂度过高可能存在重复计算尝试记忆化或空间/时间优化部分用例报错数组越界没有判断下标下限/上限检查所有dp下标访问前的条件判断01背包结果比预期大内层循环用了正序遍历改成倒序遍历完全背包结果比预期小内层循环用了倒序遍历改成正序遍历结果为0但期望非0dp没被更新到目标下标检查状态转移是否覆盖所有情况这张表是我个人debug时最常参考的清单。遇到对不上答案的情况先按这个表排查一遍比漫无目的地加打印语句高效得多。5.5 调试技巧用打印跟踪小数据最后分享一个调试小技巧当结果不对时不要直接在大数据上猜而是构造一个非常小的测试用例把整个dp表打印出来逐行手工核对。比如最少硬币问题取coins [1, 3, 4]amount 6。手工算一下dp[0]0dp[1]1dp[2]2dp[3]1用3dp[4]1用4dp[5]241dp[6]233。如果打印出来的表跟手算不一致就顺着不一致的那一行往前追很快就能定位到是初始化问题、转移方程问题还是遍历顺序问题。这个“小数据手工验证”的方法我几乎每次写动态规划都会用。它能快速区分“算法思路错了”和“代码实现错了”这两种情况避免在错误的方向上反复折腾。写在最后的一些经验做了一段时间的动态规划之后我最大的感受是它不像其他算法那样靠背模板就行而是真的需要建立一种“分而治之、逐步递推”的思维方式。初期遇到新题想不出状态定义非常正常我自己也在不少简单题上翻过车。但练了几十道典型题之后你会发现大部分题目都能归到少数几个模型里线性DP、区间DP、背包、树形DP、状态压缩DP等等。你能做的是先保证自己熟悉最核心的几类模板题理解它们为什么这样定义状态、为什么这样转移而不是死记代码。真到考试或面试的时候哪怕遇到包装得再花哨的题底层逻辑往往还是那几个经典模型之一。还有一个学习小技巧每做完一道题试着问自己三个问题——这道题用了什么状态定义方式状态转移方程能不能用自己的话讲清楚如果去掉一个维度的限制代码该怎么改这样过一遍那道题才算真正消化成你自己的东西。动态规划的扩展话题其实还有很多比如数位DP、概率DP、树形DP每个方向都能单独写一篇长文。先把这篇文章里的基础模型和避坑经验吃透后续再往那些方向深入会顺畅很多。