做算法题这些年跟圈子里的朋友交流大家公认最难啃的名字就是动态规划法。十个新手里有八个第一次看到它都会觉得这是块硬骨头状态、转移方程、最优子结构、重叠子问题术语一个接一个教材上的公式一大片真到自己动手做题的时候却不知道从哪下笔。这篇文章不是想罗列更多抽象概念而是给你一套能直接用的思考方法和做题流程。只要你能把一道递归题写出来顺着这套流程就能把它变成一道动态规划题。适合刚接触算法、准备面试笔试以及被各种“神级状态设计”劝退的读者。1. 动态规划到底在干什么先治好“重复计算”这个病1.1 从最普通的递归开始为什么斐波那契会越算越慢先说一个最简单也最经典的问题求第 n 个斐波那契数。公式大家都知道f(0)0f(1)1f(n)f(n-1)f(n-2)。绝大多数人第一次接触递推就是从这开始的也很容易写出下面这种递归代码def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)代码漂亮逻辑没问题但你把 n40 传进去试试几秒钟都不一定算得出来n45 就更夸张笔记本风扇直接起飞。原因很多人也听说过重复计算。但你有没有真正数过到底重复了多少我带你画一下调用过程。求 f(5)需要 f(4) 和 f(3)求 f(4) 需要 f(3) 和 f(2)。注意这里的两个 f(3) 本身就是完全相同的子问题但递归程序根本不记得上一个 f(3) 算出来过白白再算一遍。继续往下展开f(2) 更是被反复调用好多次。这个计算的浪费程度是指数级的。用递推式可以算出朴素递归求解 f(n) 的时间复杂度是 O(2^n)。n 从 40 涨到 42只是多了两层递归运行时间却翻了好几倍。这就是很多入门者第一次被算法复杂度打脸的时刻。问题不在“递归”本身而在“不记性”。同样的子问题算一次和算一万次结果不会有任何变化程序却傻乎乎地每次都重头推演。1.2 一张表改变一切从小问题往大问题递推理解了痛处之后解决办法其实很朴素既然 f(3) 会被反复调用那我第一次算出 f(3) 时就把它存到一个数组里后面谁要用就直接查表不用再递归展开。顺着这个思路先看最自然的两种写法。第一种叫记忆化搜索也叫自顶向下。代码还是递归的样子只是加一个缓存memo {} def fib(n): if n in memo: return memo[n] if n 1: return n memo[n] fib(n - 1) fib(n - 2) return memo[n]第二种叫自底向上递推也是我更推荐初学者掌握的写法。它的顺序恰好反过来从 f(0)、f(1) 开始一步一步往上推把结果存在数组里def fib_dp(n): if n 1: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]看到这里你应该已经感觉到了动态规划并没有多玄乎。它做的核心事情就是把大规模问题的结果拆成小规模问题的结果从小到大把所有的“中间结果”都算一遍并保存最后用这些中间结果合成最终答案。在斐波那契这个例子里dp 数组就是那张“记答案的表”填表的过程就是从小到大的递推过程。时间复杂度从指数级降到了 O(n)根本原因就是每个子问题只算一次。这件事值得单独拎出来说动态规划本质上是在用空间换时间。你多开了一个数组换来的是计算量从指数级崩塌成多项式级。后面你会看到几乎所有 DP 优化翻来覆去都是在这个“空间换时间”的基础上做文章。2. 什么样的题目才配用动态规划两个硬性条件很多同学学 DP 最大的困惑不是不会写递推而是不知道“这道题到底该不该用 DP”。有些题一眼像贪心有些题一看像二分还有些题根本看不出规律。我一般给新人的建议是先别急着套模板先拿两个标准去筛一下这题配不配用动态规划。2.1 最优子结构大问题的最优解能不能拆成子问题的最优解第一个条件是最优子结构。听起来绕口翻译成人话就是一个大问题的最优答案能不能由它内部几个小问题的最优答案直接组合出来。拿最经典的带权最短路径举例。假设你想找从 A 点经过一系列城市到 E 点的最短路线而且这条最短路线确实经过了中间城市 C。那么从 A 到 C 的这一段路线一定也是 A 到 C 的所有路线里最短的。为什么因为如果存在一条更短的 A 到 C 路线我用它替换掉原来那段整条 A 到 E 的路程还能继续变短这跟“当前已经是全局最短路”矛盾。这种“大问题最优解里天然含着子问题最优解”的性质就是最优子结构。它给了我们一个拆分问题的底气我可以放心大胆地把原问题切成若干个子问题先各自求最优再拼出原问题的最优。反过来有些问题就不满足这个性质。比如在无向图里找一条从 A 到 E 的最长简单路径路径中间经过了 C。这段 A 到 C 的路径在很多情况下并不是 A 到 C 的最长路径因为要保证整条路不能重复经过节点。你强行让子问题取“最优”反而可能破坏全局的约束条件。这类问题用 DP 或者贪心就是错的只能退回去用搜索或状压。新手分不清 DP 和贪心的时候先拿这个性质过滤一遍能避免很多无效尝试。2.2 重叠子问题递归树里重复的节点有多少第二个条件是重叠子问题。意思很好理解如果把问题拆成子问题后各个子问题之间大量存在“同一个问题被算了好几次”的情况就说明它具备重叠子问题。斐波那契数列就是最典型的例子f(5) 依赖 f(4) 和 f(3)而 f(4) 又依赖 f(3)子问题 f(3) 被反复需要。反过来看归并排序一个数组拆成左右两半左半排序和右半排序是互不相干的独立子问题彼此之间没有任何重复那就谈不上重叠子问题用普通分治就够了。所以判断用不用动态规划可以简单问自己两个问题第一大问题的最优解能不能用子问题最优解拼出来第二拆出来的子问题是不是大量重复都满足基本就可以确定走 DP 路线了。只满足第一个但不满足第二个通常用分治或贪心两个都不满足老老实实去搜索。我在实际刷题的时候还会额外加一个感受型判断方式一道题如果给你一个“规模 n”的参数暴力枚举时是指数级复杂度而且你隐隐觉得这个答案可以从小到大递推着算那八成就是 DP。这种只可意会的判断刷满三十道经典题之后自然就有了。3. 拿到DP题先别急着写码完整四步法很多新手一看到 DP 题就慌赶紧回忆背过的模板结果题目稍微变个套路就傻眼。我的建议是不管什么 DP 题你先把下面四件事想清楚再动手状态定义、转移方程、初始化、答案位置。这四个东西串起来就是完整解法。3.1 定义状态把“dp[i]表示什么”说清楚第一步是定义状态。这一点最抽象也最容易被忽视。状态说白了就是你要填的那张表的行和列分别代表什么。比如斐波那契数列里 dp[i] 表示“第 i 个斐波那契数”爬楼梯问题里 dp[i] 表示“爬到第 i 级台阶的方案总数”。定义状态有一条偷懒的技巧直接从问题本身的问法出发。题目问“最大值是多少”状态里就带上“长度为 i 时的最大值”题目问“有多少种方案”状态里就带“到第 i 个位置的方案数”题目给了两个字符串或者两堆物品通常就在状态里放两个维度比如 dp[i][j] 表示“处理到第一个串的前 i 个字符、第二个串的前 j 个字符时的答案”。状态定义一定要做到“无歧义、不遗漏、可转移”。尤其是很多字符串类题目我强烈建议统一写成“前 i 个字符”而不是“第 i 个字符”这样后面写转移和初始化都会省很多麻烦不容易出现索引越界的怪异错误。3.2 转移方程、初始化与答案定位第二步是写转移方程也就是回答“dp[i] 是怎么从前面的状态推导出来的”。怎么想转移我有一套很实用的方法叫“看最后一步”。你不要从第一项开始想而是倒过来想假设现在已经到了第 i 步到达这个状态的最后一步有哪些可能以爬楼梯为例一共 n 级台阶每次可以爬 1 级或 2 级问有多少种不同的方法爬到顶。最后一步从哪来要么是从第 i-1 级跨 1 级上来要么是从第 i-2 级跨 2 级上来。因此爬到第 i 级的总方案数就是“爬到第 i-1 级的方案数”加上“爬到第 i-2 级的方案数”。转移方程自然是 dp[i] dp[i-1] dp[i-2]。第三步是初始化。初始化不是随便设几个 0 就完了它是递推的地基地基错了整栋楼都歪。爬楼梯问题里 dp[1] 1dp[2] 2这两个边界必须单独给。很多 DP 题从 dp[0] 甚至空状态开始定义比如后面会讲的编辑距离dp[0][j] 和 dp[i][0] 都要仔细处理。第四步是确定答案在哪。有的答案是 dp[n]有的是 dp 数组里的最大值还有的是 dp[m][n] 这种二维表的右下角。这一步看起来简单但在区间型 DP 或者背包问题里答案位置很容易找错。我的习惯是写完代码前先在纸上把整个 dp 表格画出来用笔头模拟填充一遍答案在哪个格子是一目了然的。4. 三种高频DP模型照着套就行算法题里的 DP 虽然多但高频套路就那么几类。我挑三个最有代表性的模型出来线性 DP、背包 DP、字符串二维 DP。把这三类的推导过程吃透你已经能解决很大一部分 DP 题目了。4.1 线性DP最长递增子序列的推导全过程第一个模型是线性 DP代表题目是“最长递增子序列”也就是 LIS。问题描述也很简单给一个数组找出其中最长的严格递增子序列长度。注意“子序列”不要求连续这是它和“连续子数组”最大的区别。我第一次做这题时第一反应是暴力枚举所有子序列复杂度 2^n根本不可能。后来才知道用 DP 可以在 O(n^2) 内解决。状态怎么定义这里有一个关键点如果只定义 dp[i] 为“前 i 个数的最长递增子序列长度”转移会非常难写因为你不知道以谁结尾无法判断能否接上去。正确的状态是dp[i] 表示“以第 i 个元素结尾的最长递增子序列的长度”。这样转移就清晰了对于每个 j i只要 nums[j] nums[i]nums[i] 就能接到以 nums[j] 结尾的递增子序列后面长度为 dp[j] 1。遍历所有满足条件的 j取最大值。def length_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)注意 dp 数组初始化全部为 1因为每个元素都可以单独成为一个长度为 1 的子序列。答案不是 dp[n-1]而是整个 dp 数组里的最大值。这个“答案在数组里取 max”的模式在线性 DP 里非常常见新手容易漏。如果你还想继续优化LIS 有 O(n log n) 的做法核心是维护一个 tails 数组tails[k] 表示长度为 k1 的递增子序列的最小尾部元素然后用二分查找更新。代码如下import bisect def length_of_lis_optimized(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这个优化的思路就不展开细讲了面试时能写出 O(n^2) 并讲清楚 DP 思路已经算过关O(n log n) 属于加分项。4.2 0/1背包从二维递推到一维优化第二个模型是背包 DP这里只讲最核心的 0/1 背包。问题描述有 n 个物品每个物品有重量 weights[i] 和价值 values[i]背包容量为 capacity每个物品最多选一次问能装的物品最大总价值是多少。状态定义是二维的dp[i][j] 表示“考虑前 i 个物品背包容量为 j 时能获得的最大价值”。为什么要两维因为既要记录处理到哪个物品又要记录剩余容量。转移时对于第 i 个物品只有两种决策不选它那么状态从 dp[i-1][j] 原样继承价值不变选它前提是 j weights[i]那么状态从 dp[i-1][j - weights[i]] 转移过来再加上 values[i]。所以转移方程是def zero_one_knapsack(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]我这里直接给的是空间压缩后的写法dp 从二维变成一维。原理是计算第 i 个物品时只需要上一轮的结果。但压缩后遍历容量 j 必须从大到小也就是倒着遍历。为什么因为如果正序遍历dp[j - weights[i]] 可能已经被当前这个物品更新过了等于把同一个物品重复选了多次这就不是 0/1 背包而是完全背包了。倒序遍历能确保 dp[j - weights[i]] 还是上一轮也就是还没装当前物品的值。这个倒序遍历是背包问题最经典的坑没有之一。面试时我经常先故意写成正序再问对方“为什么结果不对”绝大多数人表达不清楚。你只要把这一点彻底吃透0/1 背包基本就掌握了。4.3 二维字符串DP编辑距离第三个模型是字符串类二维 DP代表题是编辑距离。题目要求给你两个单词 word1 和 word2每次操作可以插入一个字符、删除一个字符或者替换一个字符计算把 word1 变成 word2 所需的最少操作次数。状态定义很自然dp[i][j] 表示把 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。注意这里是“前 i 个”也就是从 1 计数比 0 计数好处理。代码实现如下def min_distance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] 1, # 删除 word1 的一个字符 dp[i][j - 1] 1, # 插入一个字符到 word1 dp[i - 1][j - 1] 1 # 替换一个字符 ) return dp[m][n]先看初始化dp[i][0] 表示把 word1 的前 i 个字符变成空串只能全删所以是 idp[0][j] 表示把空串变成 word2 的前 j 个字符只能全插所以是 j。这两行是二维表的地基。再看转移如果两个字符相等那这一位不需要额外操作直接继承前一位的状态 dp[i-1][j-1]如果不相等则考虑三种操作的最小值。这个题活生生展示了二维 DP 的填表逻辑每个格子只依赖左、上、左上三个方向你在纸上手动填一遍 3x3 的表所有转移一下就通了。刷 DP 题时像编辑距离这种二维问题我建议一定要在纸上画几次表格。很多人代码写了半天不知道怎么错其实只要手算一个小数据就立刻明白了。5. 优化与实现细节这些坑我替你踩过了基础写法会了之后接下来是实战中绕不开的优化与细节问题。很多时候你的思路是对的但代码就是跑不过问题基本都出在这一节讲到的几件事上。5.1 自顶向下记忆化与自底向上填表怎么选理解了 DP 的原理之后新手往往会陷入一个纠结记忆化搜索和递推填表到底用哪个我个人的习惯是分阶段。如果你是在学习阶段对题目思路还不清晰我强烈建议先写记忆化搜索。因为它跟你熟悉的递归结构基本一致只需要加一个缓存数组思维负担最小。一旦递归的终止条件和调用关系写对了状态转移也就跟着对了不容易出现递推循环顺序写错的低级错误。如果是正式比赛、面试手写或者追求性能的场景我更推荐自底向上的递推。因为递推没有递归调用栈的额外开销也不用担心递归深度太大导致栈溢出。Python 的默认递归深度大概在 1000 层左右但有些 DP 题的状态依赖链可能超过几万层递归就炸了。其实两者在很多情况下可以互相转换。我的标准流程是先用记忆化搜索快速理清状态转移确认正确后再翻译成自底向上的递推版本最后按需做空间优化。对比维度自顶向下记忆化自底向上递推代码直观程度接近递归容易理解需要手动控制计算顺序递归栈风险深度过大会溢出无栈风险状态计算范围只算被依赖的状态可能多算无关状态常用场景思路不清晰时快速验证性能要求高的正式提交5.2 滚动数组空间压缩时必须搞懂的遍历方向空间优化是 DP 从“能跑”迈向“跑得好”的关键一步。很多二维 DP 其实每一刻只需要上一行的数据比如编辑距离dp[i][j] 只用到 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]所以理论上只需要两行数组滚动使用可以把空间从 O(m*n) 降到 O(n)。滚动数组最简单的做法是用两个一维数组交替保存old 和 new每一轮计算完再互换。但更常见也更考验人的是像 0/1 背包那样的单数组覆盖。单数组覆盖时遍历方向必须分清楚0/1 背包容量 j 需要倒序遍历防止同一个物品被重复选择。完全背包每个物品可以选无限次容量 j 需要正序遍历因为要允许重复选择当前物品。很多同学把这两个搞混背答案是记不住的。我提供一个理解角度单数组覆盖时倒序表示“这一轮更新时被依赖的数据还是上一轮的”正序表示“被依赖的数据随时可能被本轮结果覆盖”。你想让当前物品能不能被选多次就决定让容量往哪个方向走。只要把这个想通以后再遇到“正序还是倒序”的题都不会再错。5.3 状态设计与索引细节初值、-inf、开n1最后一个特别磨人的点是细节。我在指导别人改代码时发现大部分超出样例的错误都出在三类细节上。第一dp 数组开的大小。状态里有 i 和 j 两个维度时数组要开成 (n1) 的大小。因为你用的往往是“前 i 个”这种从 1 开始计数的语义0 留给空集或空串。漏开一位是索引越界的头号原因。第二初始值的含义要分清楚。DP 求最大值时有些状态根本不可达不能初始化为 0而是要初始化为一个很小的负数比如 float(-inf)。举个例子背包问题里如果物品重量有大有小dp[j] 的某些 j 值可能根本无法由任何物品的组合达到初值为 0 在很多情况下也没问题但在另一些“恰好装满”的变种题里初值为 0 就会让非法状态也参与转移结果全是错的。第三注意数值范围。方案数类 DP 很容易突破 int 范围Python 本身没有这个问题但如果用 C 就要记得上 long long。我见过太多人题目没特意提醒结果用 int 一测大样例直接溢出成负数检查半小时不知道错在哪。这四件事可以在写代码之前先确认一遍能省掉大量调试时间。6. 常见Bug排查与调试点做 DP 题最气人的是代码看着啥都对一跑就错。我把这几年遇到的常见 Bug 整理成了下面几张“病历”每一条都配了对应的排查方法希望对你有用。6.1 转移方程写反是最隐蔽的错误临床表现为小数据能过大数据莫名其妙错。多半是状态转移依赖的方向搞反了。比如最长递增子序列正确写法是拿 j i 的状态去更新 dp[i]有人一着急写成从 i 往后面更新最后 max 出来的结果偏大或偏小还很难肉眼发现。排查方法很笨但很有效挑一个长度 5 以内的测试用例把 dp 数组在每轮循环后的值打印出来亲手画一遍推导过程。只要代码和手推结果对不上错误位置立刻暴露。写 DP 题时脑子里要始终清楚“当前状态依赖哪些更小的状态”一旦依赖关系不明确就先把手推过程写出来再动键盘。6.2 初始化漏掉边界答案永远不对初始化错误是另一种高频 Bug。典型表现是空串、空数组、容量为 0、台阶只有 1 级这类“边界小状态”没处理导致所有转移都建立在错误的地基上。以编辑距离为例dp[0][j] 表示从空串变到目标串只能靠不断插入字符所以必须初始化成 j。如果你漏了这行后面所有 dp[1][1] 的计算都会用到错误数据最后答案差得离谱。我建议拿到一道新 DP 题先在草稿纸上写出 0、1、2 这三个最小规模的手算答案再回头检查初始化能不能推出这些值能对上再开始写全套代码。6.3 调试三板斧打表、暴力对拍、手推小样例说到底层调试技巧我习惯用三板斧。第一板斧是打表。把中间 dp 数组每一轮打印出来观察数值是不是逐层合理递推。状态数不多时直接肉眼找规律状态多就挑几行打印不全部输出。第二板斧是暴力对拍。自己写一个完全不用 DP 的暴力解比如枚举所有可能方案和 DP 结果对比。随机生成小规模数据跑几百组一旦输出不一致就把那一组数据缩小后再找到最小复现用例。这是我现在做算法题最依赖的方法没有之一。第三板斧是手推小样例。我特别推荐用纸笔推一个 3x3 或者 5 个元素的小表从初始化开始一格一格填。很多时候填完一遍代码里哪里写反了、哪里多加了 1自己在填表过程中就意识到了。别嫌麻烦这一招对二维 DP 尤其有用。我常跟身边朋友说DP 题卡住的时候困在人脑里复盘代码是最低效的。去洗手间冷静一下回来画一张小表或者对拍一个暴力解往往几分钟就能定位问题。最后说一点个人经验。动态规划法最劝退人的地方其实是心理门槛。很多人老想着“我要一眼想到巧妙的转移方程”其实没必要。初学者做 DP就应该多写暴力递归把子问题的调用关系看清然后一步一缓存再翻译成递推。我见过很多“DP 学不明白”的人最后都是靠这个方法慢慢开窍的。刷题不需要急把状态定义说清楚、把转移方程推导明白顺手能把边界值验一遍代码只是最后一步的翻译工作。