我见过太多这样的场景：有人能把“最优子结构”“重叠子问题”“状态转移方程”这几个词背得滚瓜烂熟，可拿到一道新题，十分钟过去还是写不出第一行代码；也有人刷了一大堆DP题，经典模板都背下来了，题目换个说法就彻底不认识了。动态规划在算法学习和工程优化里的位置非常特殊，说它是“算法能力的试金石”一点不夸张——它考的不是记忆，而是你把一个问题重新建模成子问题链的能力。
这篇文章我想老老实实把动态规划从思考方式到解题步骤再到经典例题完整讲一遍。不堆抽象概念，而是带着你从“敢写递归”一步步走到“空间优化后的递推代码”，中间每一步为什么这么走、依赖关系怎么理、初始化要注意什么，全都会说清楚。适合刚入门准备系统性刷题的同学，也适合工作中需要处理路径规划、资源分配、序列比对等优化问题的开发者。文章里的代码以Python为主，思路完全通用，用其他语言对照着写也行。
1. 三个底层概念先掰明白：最优子结构、重叠子问题、状态定义
1.1 最优子结构：大问题为什么能拆开算
动态规划能成立的第一个前提，是最优子结构。用大白话说，就是：一个全局最优解，它拆出来的每一段子问题的解，也必须是那个子问题的最优解。
想象一下你要从城市A开车到城市D，中间必须经过B和C。如果有一条路线被证明是从A到D的最优路线，那么从A到B这一段，也一定是从A到B的所有路线里最优的那一条。为什么？因为如果存在一条更短的A到B路线，你只要把原路线里A到B这一段替换掉，整条A到D路线就变得更短了——这就和“原路线已经最优”矛盾了。
很多问题天然具备这个性质，比如最短路径、编辑距离、背包问题；也有很多问题不具备，比如某些全局最优方案里的局部片段反而“走得偏”才能给后续腾出优势。这类问题用动态规划就会出问题，更适合贪心或者搜索。所以拿到一道题，第一件事不是急着写转移方程，而是先问自己：这个大问题能不能拆成几个独立的、可递推的小问题？
1.2 重叠子问题：递归慢在哪，记忆化救的是什么
最优子结构说的是“能拆”，重叠子问题说的是“拆了之后有大量重复计算”。这两个性质一起出现，动态规划才值得用。
以斐波那契数列为例。f(5) = f(4) + f(3)，而f(4)自己又会去算f(3)、f(2)……如果把整个递归过程画成一棵树，你会发现f(2)被算了三次，f(3)被算了两次。n小的时候无所谓，n到40左右，普通递归已经要算上亿次；n到100，任何机器都跑不动。
动态规划的应对思路极其朴素：**算一次，存一次，下次直接查表。**这就是缓存，也是后面所有DP实现的共同地基。很多人觉得“记忆化搜索”和“动态规划”是两个东西，其实它们解决的是同一个问题——重叠子问题，只是一个用递归加缓存的姿势，一个用循环填表的姿势。
1.3 状态定义：先想清楚dp[i]到底存什么
真正让初学者卡住的，或者说让DP从“背模板”变成“需要理解”的地方，是状态定义。dp[i]到底代表什么？这是所有后续推导的地基。
没有任何公式可以直接生成状态定义，但它有很强的规律可循：
- 一维DP的状态，绝大多数是“前i个元素怎么怎么样”，或者“以第i个元素结尾怎么怎么样”；
- 二维DP的状态，通常是“第一个序列的前i个与第二个序列的前j个怎么怎么样”；
- 背包类问题会在“前i件物品 + 容量j”这两个维度上做文章。
状态定义定了，转移方程基本是顺着语句抄一遍。我辅导过不少同学，十个里有八个卡在状态定义这一步：要么定义得太模糊，导致转移方程怎么想都想不出来；要么定义里掺入了决策（比如“第i间必偷的最大值”），导致后续处理变复杂。所以，定义状态是DP里唯一需要“想”的部分，后面全是流程化操作。
2. 完整推导一次爬楼梯：从暴力递归一步步变成递推数组
2.1 敢写递归：把“怎么走”翻译成“怎么调用自己”
爬楼梯是最经典的入门题：有n级台阶，每次可以走1级或2级，问一共有多少种不同的方式走到顶部。
很多人觉得这题太简单，不值得认真推导。但我想说，这道题包含了DP从原形到最终形态的全部过程，值得掰开揉碎看一遍。
先别想DP，只问自己一个问题：**最后一步是怎么走的？**答案只有两种——从第n-1级迈1级，或者从第n-2级迈2级。那么到第n级的方式数，天然等于“到第n-1级的方式数”加上“到第n-2级的方式数”。这句话翻译成代码，就是暴力递归：
# 暴力递归：直接把上面的逻辑翻译过来 def climb_recursive(n): if n <= 2: return n return climb_recursive(n - 1) + climb_recursive(n - 2)这里的边界条件n <= 2也很直觉：1级台阶只有1种走法，2级台阶有“1+1”和“直接跨2级”两种走法，所以返回n。
很多人第一次看这段代码时，会怀疑这是不是太简单了，和动态规划有什么关系？关系大得很。**递归写的是问题的定义，递推数组写的只是执行顺序的优化。**你把这个定义写出来，就已经完成了DP最难的一半。
2.2 加缓存：记忆化搜索就是DP的草稿
暴力递归的毛病很明显：重复计算。想想看，climb_recursive(5)会调用climb_recursive(4)和climb_recursive(3)，而climb_recursive(4)又会调用climb_recursive(3)和climb_recursive(2)。这个climb_recursive(3)就被算了两遍。n越大，这种重复呈指数级增长。
解决办法就是加一个缓存，算过的值直接存下来，下一次遇到同样的入参不再递归，直接返回：
# 记忆化搜索：用缓存干掉重叠子问题 memo = {} def climb_memo(n): if n <= 2: return n if n in memo: return memo[n] memo[n] = climb_memo(n - 1) + climb_memo(n - 2) return memo[n]加了这一层缓存之后，每个n只需要被真正计算一次，递归树被剪成一条链，时间复杂度从指数级降到了线性级。到这一步，“重叠子问题”这个抽象概念已经变成了一行具体的代码——这就是动态规划的草稿版，自上而下思考，自下而上填充。
2.3 换数组：递推顺序背后的依赖关系
记忆化搜索虽然能运行，但有两个小问题：一是递归调用有函数栈开销，n特别大时可能爆栈；二是“自上而下”的调用顺序，让你很难直观看到状态之间的依赖关系。于是我们把递归翻成循环形式的递推填表：
# 动态规划：自下而上填表 def climb_dp(n): if n <= 2: return n dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]注意这里的遍历顺序：从3到n正着填。为什么？因为dp[i]依赖的是dp[i-1]和dp[i-2]，这两个状态必须已经在dp[i]被计算之前算出来。依赖方向决定了遍历顺序，这是DP里一条永远成立的规律。
最后你还会发现，整个dp数组在计算过程中只用到前两个值，后面的值用过就再也用不到了。于是数组都没必要开满，用两个变量滚动就够了：
# 空间优化：滚动变量 def climb_opt(n): if n <= 2: return n a, b = 1, 2 for _ in range(3, n + 1): a, b = b, a + b return b爬楼梯这一题，从暴力递归到记忆化到递推数组再到滚动变量，每一步都有明确动机，没有一步是为了炫技。你能亲手走一遍这个过程，后面遇到再复杂的DP，思考路径也都是这一条的延长线。
3. 解题五步法：用“打家劫舍”把这套流程走一遍
3.1 定状态：dp[i]的含义直接决定后续所有代码
“打家劫舍”是另一个非常经典的一维DP：一排房子，每间房子里有一定金额，不能偷相邻的两间，问最多能偷到多少钱。
这道题比爬楼梯稍微进了一步，因为它的转移方程不是直接“加法”，而是带决策的“取最大值”。按五步流程走，第一步永远是定状态。这里我用“前i个房子”这个口径：
dp[i] = 考虑前i个房子（也就是索引0到i-1）时，能偷到的最大金额。
为什么用“前i个”而不是“第i个”？因为用“前i个”配合长度为n+1的数组，空房子（0个）就有一个明确的占位，初始化和边界判断都会顺手很多。这一点后面还会展开讲。
3.2 写转移方程：这一步需要的是“可能性枚举”
状态定义定了，转移方程就是枚举当前房子的所有可能：
- 不偷第i个房子，那最大金额就是dp[i-1]；
- 偷第i个房子，那相邻的第i-1个房子不能再偷，所以最大金额是dp[i-2] + nums[i-1]。
两者取最大值：
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
我第一次写这道题时，总觉得应该写dp[i-1] + nums[i]之类的变体，但顺着“偷/不偷”两个分支想，思路就特别清晰。转移方程本质上是把所有到达当前状态的可能性列出来，再按题目要求取max、取min或者求和。很多初学者卡在转移，其实是没把“当前状态有哪些前驱状态”枚举完整。
代码实现：
def rob(nums): n = len(nums) if n == 0: return 0 if n == 1: return nums[0] dp = [0] * (n + 1) dp[0] = 0 # 没有房子，收益为0 dp[1] = nums[0] # 只有一间房子，那就偷它 for i in range(2, n + 1): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) return dp[n]3.3 初始化与遍历顺序：最容易丢分的地方
初始化本质上是把“最小的子问题”手算清楚。在打家劫舍里，最小的子问题是dp[0]和dp[1]：0间房收益当然是0，1间房收益就是这间房的金额。这两个值定了，后面的递推才有起点。
遍历顺序同样由依赖关系决定：dp[i]依赖dp[i-1]和dp[i-2]，所以从2到n正着遍历。这里没有什么需要“猜”的，看你依赖谁，就知道谁得先算完。
常见错误是把dp[2]提前初始化成一个“看起来合理”的数值，导致后续全部偏移。我的习惯是：先写转移方程，再把递归的边界条件翻译成初始化的具体值，不要凭感觉加额外初始化。
3.4 空间压缩：有些时候只用两个变量就够了
转移方程里dp[i]只依赖dp[i-1]和dp[i-2]，和爬楼梯的情况一模一样，完全可以用两个滚动变量替代整个数组：
# 空间优化到O(1) def rob_opt(nums): prev2, prev1 = 0, 0 for x in nums: prev2, prev1 = prev1, max(prev1, prev2 + x) return prev1这里prev2对应dp[i-2]，prev1对应dp[i-1]，每处理一个新房子就滚动一次。很多人在面试里被问到“能不能优化空间”，指的就是这一步。以后遇到任何“dp[i]只依赖前面固定几个值”的转移，都可以照这个方法压缩。
4. 0-1背包：二维DP的经典模型与一维空间压缩
4.1 背包问题的状态有两维：选到第几个、还剩多少容量
如果说前面几道题是一维DP的地基，那0-1背包就是把维度撑到二维的分水岭。题目是这样：有n件物品，每件有自己的重量w[i]和价值v[i]，背包能承受的最大重量是W，每件物品只能选择“拿”或“不拿”，问能装进背包的最大总价值是多少。
为什么这个问题不能用一个一维的dp[i]解决？因为“考虑前i件”这个信息里，没有承载“重量限制”这个维度。同样的前i件物品，在不同剩余容量下能获得的最大价值是不同的。所以状态必须同时记录两个信息：
dp[i][j] = 从前i件物品中选择，总重量不超过j时，能获得的最大价值。
这就是二维DP的标准定义方式。第一维管“物品编号”，第二维管“容量”，两个维度互相约束。
4.2 二维表怎么填：用一组具体数据把过程走一遍
有了状态定义，转移方程顺理成章。处理第i件物品时，只有两个选择：
- 不拿第i件：价值保持为dp[i-1][j]；
- 拿第i件：前提是当前容量j大于等于w[i-1]，价值为dp[i-1][j-w[i-1]] + v[i-1]。
两者取最大值：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
为了不空谈，我找一组具体数据手算一遍。假设3件物品如下：
| 物品编号 | 重量 | 价值 |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 1 | 2 |
| 3 | 3 | 3 |
背包容量为4。初始时dp[0][j]这一行全是0，因为一件物品都不选，价值当然是0。接下来逐行填表：
| 容量j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 只考虑第1件 | 0 | 0 | 4 | 4 | 4 |
| 考虑前2件 | 0 | 2 | 4 | 6 | 6 |
| 考虑前3件 | 0 | 2 | 4 | 6 | 6 |
看第三行：容量为3时，可以同时拿第1件（重2、值4）和第2件（重1、值2），总重量正好3，总价值6。第三件重量3、价值3，容量3时拿它只值3，不如6。容量4时，拿第1、2件已经是6，第3件拿不拿都无法超过，所以答案就是6。
这种手工填表的过程，比背十遍转移方程都有用。先用小样例把表格走一遍，你才能真正知道每个格子是怎么来的。
代码实现：
def knapsack_2d(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): if j < weights[i - 1]: dp[i][j] = dp[i - 1][j] # 放不下，只能不拿 else: dp[i][j] = max( dp[i - 1][j], # 不拿 dp[i - 1][j - weights[i - 1]] + values[i - 1] # 拿 ) return dp[n][capacity]4.3 一维数组改造：为什么容量必须倒着遍历
二维版本的空间复杂度是O(n*W)，物品多或容量大时内存扛不住。观察转移方程你会发现，dp[i][...]这一行只依赖dp[i-1][...]那一行，再往前的行完全用不到。所以我们可以只保留一行，把二维数组压成一维：
def knapsack_1d(weights, values, capacity): dp = [0] * (capacity + 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity]注意内层循环的j是倒着遍历的，这是0-1背包一维化里最关键、也是最容易被忽略的细节。
为什么必须倒着？想象一下如果你让j正着从0到capacity遍历：当你在更新dp[j]时，dp[j - weights[i]]可能已经在同一次外层循环里被更新过了。也就是说，这个值已经包含了“当前这件物品”的贡献。你再拿它加values[i]，相当于同一件物品被拿了多遍。正序更新得到的是完全背包（每件物品可以无限拿），倒序更新才能保证每件物品最多拿一次。
之所以倒序安全，是因为dp[j - weights[i]]在倒序时还没被本轮更新，它仍然保存着上一轮（也就是没拿当前物品时）的值。这一点理解了，你就再也不会搞反0-1背包和完全背包的遍历顺序。
4.4 常见变体：恰好装满、方案计数、最少个数
背包题在算法题里能变出很多花样，但都是在这套转移方程上做文章：
恰好装满：如果题目要求“正好把容量W装满”，初始化就不能全部给0，而是dp[0]=0，其余dp[j]=负无穷，或者一个足够小的数。原因是“恰好装满”意味着每个状态都必须由真实可选的组合拼出来，不存在的东西不能默认0。
求方案总数：把转移方程里的max改成求和。dp[j] = dp[j] + dp[j - weights[i]]，含义是“达到容量j的方案数等于不用当前物品的方案数加上用当前物品的方案数”。
求最少物品个数或最小价值：把max改成min，同时初始化正无穷。这类题刷起来特别多，但搞清楚母题后，变体只是改一两个字母。
5. 编辑距离和最长公共子序列：二维DP的表格套路
5.1 最长公共子序列：相等和不相等两种情况的处理
最长公共子序列（LCS）是面试里出现频率极高的题：给定两个字符串s1和s2，找出它们最长的公共子序列长度。注意子序列不要求连续，只要保持相对顺序。
这道题看到“两个字符串”，直接反应是二维DP。定义状态：
dp[i][j] = s1的前i个字符与s2的前j个字符的最长公共子序列长度
转移分两种情况：
- 如果s1[i-1] == s2[j-1]，说明当前字符可以匹配上，长度在dp[i-1][j-1]的基础上加1；
- 如果不相等，那这两个字符至少有一个不在最终公共子序列里，所以取“去掉s1的第i个字符”和“去掉s2的第j个字符”这两种情况的最大值。
def lcs(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]这里dp数组特意做成(m+1)*(n+1)，目的就是给“空串”留位置。第一行和第一列初始化全0，表示空串和任何字符串的公共子序列长度都是0。
5.2 编辑距离：把删除、插入、替换写成转移方程
编辑距离和LCS是“一类题”的两个方向。编辑距离问题描述是：允许对字符串做三种操作——插入一个字符、删除一个字符、替换一个字符，每种操作代价都是1，问把s1变成s2最少需要多少次操作。
状态定义几乎一模一样：
dp[i][j] = 把s1的前i个字符变成s2的前j个字符所需的最少操作数
初始化是这题的一个考点：dp[i][0] = i，意味着把s1的前i个字符全部删掉才能变成空串；dp[0][j] = j，意味着从空串插入j个字符才能变成s2的前j个。
转移方程同样分两种：
- s1[i-1] == s2[j-1]，当前字符不用动，直接继承dp[i-1][j-1]；
- 不相等，就需要从三种操作里选代价最小的：
- 删除：dp[i-1][j] + 1，删掉s1的当前字符；
- 插入：dp[i][j-1] + 1，在s1中插入一个和s2[j-1]相同的字符；
- 替换：dp[i-1][j-1] + 1，把s1[i-1]直接换成s2[j-1]。
def edit_distance(s1, s2): m, n = len(s1), len(s2) 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 s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min( dp[i - 1][j] + 1, # 删除 dp[i][j - 1] + 1, # 插入 dp[i - 1][j - 1] + 1 # 替换 ) return dp[m][n]这里有个很妙的对称性：插入和删除本质上是一个操作从两个方向看。站在s1的角度是删除，站在s2的角度就是插入，所以转移方程里这两个方向都出现，min取最小即可。
5.3 从dp表反推答案：追着转移方向走回去
很多场景不光要长度/距离，还要具体方案。比如文本对比工具，除了告诉你两段文本差多少，还要把差异标出来。这时就需要从dp表反推。
以LCS为例，从dp[m][n]开始往回走：
- 如果s1[i-1] == s2[j-1]且dp[i][j] == dp[i-1][j-1] + 1，说明这个字符确实被选进公共子序列了，记下它，然后斜着走到(i-1, j-1)；
- 否则，比较dp[i-1][j]和dp[i][j-1]，哪个大就往哪个方向走；如果相等，任选一个方向（这对应多个不同子序列的情况）。
反推的代码并不复杂，但它要求你保留完整的二维表。这也引出了一个重要提示：如果题目要求输出方案，空间压缩就要三思，因为滚动数组会把中间状态丢掉。
5.4 二维DP通用套路：先画表，再找依赖方向
LCS和编辑距离看多了，你会发现这类“两个序列”的二维DP有非常固定的套路：
- 字符串匹配、序列比对、相似度计算这类关键词出现时，第一反应就是二维DP；
- 状态定义总是“dp[i][j] = 第一个序列前i个与第二个序列前j个的某个指标”；
- 转移方程就是在“当前两个字符相等/不相等”两个分支下分别讨论；
- 从哪个方向转移而来，就决定了表格的填充顺序。
我自己的习惯是在草稿纸上先画一张小表，手算几格，再写代码。空想状态转移很容易绕晕，但表格画出来，依赖方向一目了然。这比任何口诀都管用。
6. 刷DP题最常翻车的三件事：初始化、遍历顺序与滚动数组
6.1 下标差一：数组长度n+1到底好在哪
DP代码里最常见的bug，是“差一错误”。我见过太多人写循环时用错了下标，或者取元素时多取了少取了一个。
用n+1长度的数组，核心好处是给“空状态”一个位置。字符串题目里的空串、背包题里的0件物品、打家劫舍里的0间房子，全部落在dp[0]这个位置上。代价是你在取原始数据时要记得做一次偏移：比如物品重量是weights[i-1]，房子金额是nums[i-1]，而不是weights[i]。
如果你用的是“以第i个元素结尾”这种状态定义，数组长度可以正好是n，取元素也不需要偏移。两种口径都正确，但绝不能在一道题里混用。A同学有一次debug到怀疑人生，最后发现就是某个循环里看的是nums[i]，另一个循环里写的是nums[i-1]，状态定义的口径完全对不上。写代码前先确认口径：dp的下标到底是“数量”还是“索引”。
6.2 遍历顺序：什么时候正序、什么时候倒序、能不能换
遍历顺序是DP里最容易“背错”的部分，尤其是背包。我的建议是不要背结论，而是从依赖关系现场推：
- 如果当前状态依赖的“前驱状态”来自上一轮计算（上一件物品、上一个字符），那这一轮更新时就不能提前覆盖它们，背包倒序遍历的原因就在这里；
- 如果当前状态依赖的是本轮已经算出的更小状态，那就要看题目允许不允许这种“重复使用”。完全背包允许重复拿物品，所以正序；0-1背包不允许，所以倒序；
- 对于LCS、编辑距离这种二维表格，由于每个格子依赖的是左边、上边和左上角，只要两层循环方向都是从左到右、从上到下，就不会出问题。
还有一个我自己的经验：不确定时，就把二维表的过程在脑子里走一遍。比如0-1背包，容量倒序的本质是“锁住上一行的值”，你理解了这一点，就再也不会把两个版本的代码弄混。
6.3 滚动数组的代价：想在最后反推方案时会吃亏
前文反复提到滚动数组能把空间从O(n)降到O(1)，但它不是免费的。滚动数组只保留“最近几行”的值，一旦题目要求输出具体方案——比如选了哪几件物品、最长公共子序列到底是什么、编辑距离的每一步操作是什么——纯滚动数组的信息就不够了。
这时候有几种做法：
- 保留完整的二维表，空间换方案；这是最直接的做法；
- 额外开一个决策数组，在每步转移时记录“是从哪个方向来的”，最后靠这个数组反推；
- 部分问题还可以在最后做一次“暴力反推”，但前提是你保留了足够定位的状态信息。
所以我在做题时的习惯是：**先按完整二维表把思路捋清楚并保证正确，再考虑要不要滚动数组优化。**优化是加分项，但不是所有题目都该做。
6.4 别对每道题都用DP：先判断有没有最优子结构
最后想泼一盆冷静水：动态规划不是万能的，也不是每道优化题都必须用DP。判断一道题适不适合DP，就看两个性质：有没有最优子结构，有没有重叠子问题。前者保证了“能拆”，后者决定了“拆了值得”。
举个反例：假设有面额为1、5、11的硬币，要凑出15元。贪心策略是每次取最大面额，先拿11，剩下4元用4个1元补齐，一共需要5枚硬币。但最优解其实是3个5元硬币，只要3枚。这道题贪心会翻车，因为它不具备“贪心选择性”，而DP恰好能处理这种需要全局权衡的场景。反过来，比如活动安排这种“选完之后不影响后面选择”的问题，贪心又快又对，你用DP反而绕远。
我的判断流程是：先试着把问题写成递归定义，看看能不能自然拆出子问题；如果能拆，再看拆出来的子问题是否会被反复计算。两个条件都满足，再进入状态定义的环节。如果缺了其中任何一个，就该考虑换思路了。
学动态规划，我认为最值得养成的习惯不是刷题量，而是先写递归、再画表格、最后写递推这个“三步走路”。这个顺序看着绕，但它能确保每一步的动机清楚，不会出现“代码能跑但说不清为什么”的黑箱状态。动态规划与其说是一个算法，不如说是一种把思考显式化的习惯。状态定义清楚、依赖关系理顺、边界条件填对，剩下的事情其实都是水到渠成。用到后来你会发现，真正难的从来不是写代码，而是肯不肯静下心，先把问题重新定义一遍。
