写过一道动态规划题之后最难的可能不是这道题本身而是下一道题。很多学 LeetCode 的小白刷到动态规划这一块都会经历一段类似的痛苦网上找题解状态转移方程抄下来看着也简单但等下次遇到同类题大脑仍然一片空白。于是开始怀疑自己是不是天赋不行最后得出一个结论——动态规划太难了。这篇文章想先给一个明确判断动态规划不是背出来的是推出来的。真正让新手卡住的不是公式难懂而是不知道公式是怎么来的。只要把推导链路理顺——从暴力递归到记忆化搜索再到递推 DP——你会发现所谓状态转移方程只是把“暴力搜索”换了一种更省事的写法。今天这篇是“小白怎么刷 LeetCode”系列的第 9 篇会带你从递归一步步推到 DP并且把 LeetCode 刷题里最常遇到的三类动态规划模型都覆盖一遍背包问题、LIS最长递增子序列、LCS最长公共子序列。你不必一次记住所有模板但你可以借这三类题建立一套自己的动态规划推导方法。1. 这篇文章真正要解决的问题先说一个很典型的刷题场景。你在 LeetCode 上搜“动态规划”热门题一打开题解区高赞回答写得都很“优雅”定义dp[i]、状态转移、初始化、返回答案四步走清清楚楚。你点点头觉得懂了于是关掉题解自己写。结果发现第一步dp[i]到底表示什么就已经开始纠结了。很多人的问题就在这里一上来就学别人的状态转移方程跳过了最重要的“为什么是这个方程”的推导过程。这就好比有人告诉你“答案等于 7”但没告诉你这题目在算什么下次换个数字照样不会。这篇文章要帮你解决的不是让你背更多模板而是改变你面对动态规划题目时的反应。读完你会有三个收获遇到 DP 题第一反应不是“这题用哪个公式”而是“先写一个暴力递归试试”知道怎么把递归改写为记忆化搜索再改写为递推 DP掌握背包、LIS、LCS 这三个高频模型的推导套路并能看出它们的共同点。什么样的读者最适合看这篇文章主要面向已经开始刷题但被 DP 题反复卡住的小白也适合正准备面试算法却对动态规划心里没底的开发者。如果你已经能独立 A 掉 LeetCode 中等难度 DP 题这篇文章帮你做一次方法论的梳理也会有参考价值。2. 动态规划到底在解决什么问题很多人觉得动态规划是算法分类里的一个高深分支其实它不是。一句话解释动态规划是“避免重复计算的暴力搜索”。想象你从办公室走去公司楼下便利店如果天生路痴每次走都要把所有岔路口都试一遍这叫暴力搜索。但你走两次之后发现从 3 楼电梯口到 1 楼大门的最短路径根本不需要每次从头决定。你把这个结果记下来下次直接走这就是动态规划。放在算法题里有两个关键特征第一个特征叫重叠子问题。一个大问题被拆成几个小问题而这些小问题会被反复计算。最典型的是斐波那契数列计算fib(5)需要fib(4)和fib(3)但计算fib(4)又要算一次fib(3)于是fib(3)被重复算了两次。随着 n 变大这种重复是指数级增长的。第二个特征叫最优子结构。一个大问题的最优解可以由子问题的最优解推导出来。比如求“到第 10 级台阶的走法数量”你只需要知道“到第 9 级台阶”和“到第 8 级台阶”的走法数量因为最后一步只可能跨 1 级或 2 级。判断一道题能不能用动态规划就看这两点同时成立。如果一个问题既没有重叠子问题又没有最优子结构那它多半不适合用 DP 解。这也是为什么很多教程建议初学者从暴力递归入手。递归天然就在描述“大问题拆成小问题”的过程。你从递归入手实际上是在把 DP 题翻译成“函数调用”的普通题目。等递归的重复计算点暴露出来再用 DP 去优化思路就是顺理成章的了。3. 从递归到 DP一条万能的推导路线动态规划新手的痛点是总想一步到位写出dp数组。别急着跳进数组先走完下面这三步第一步先写暴力递归。不要管效率只问自己这个问题的答案能不能用一个递归函数表达递归函数最舒服的写法是“定义状态 边界条件 状态转移”也就是把问题原封不动“翻译”成代码。第二步加上一个缓存把重复计算去掉。递归还是原来的递归但每次算完结果就存起来。下次遇到相同参数直接返回缓存。这一步产生的算法叫记忆化搜索它通常已经能通过很多中等难度的 LeetCode 题了。第三步把“递归 缓存”改写成循环。从最简单的边界条件开始一个一个往上推用数组代替函数调用栈。这就是传统意义上的迭代 DP。用斐波那契数列来演示一下。先写最朴素的递归def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这个版本在 n 很小时没问题但 n 稍大就非常慢因为大量子问题被重复计算。如果画出调用树你能看到fib(2)被调用了很多次。加上缓存改成记忆化搜索def fib_memo(n): memo {0: 0, 1: 1} def dfs(x): if x in memo: return memo[x] memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)递归写法只是把“当前问题依赖两个子问题”表达清楚了真正让它变快的是 “memo” 这个缓存。现在我们把它改写成自底向上的递推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]这三个版本解决的是同一个东西区别只是计算顺序。但从理解角度看写出第一种递归是基础第二种是桥梁第三种才是很多题解里给的“标准答案”。所以别再把“不会写状态转移方程”当成障碍。准确地说你是还没有找到那个描述子问题的递归函数。下一节我们就用一个 LeetCode 经典题走一遍完整推导。4. 用一道题学会推导爬楼梯LeetCode 70 题“爬楼梯”是动态规划最经典的入门题。题目描述很简单你每次可以爬 1 级或者 2 级台阶问爬到第 n 级台阶一共有多少种不同的走法。如果直接想递推公式很多新手看答案会觉得很突然。我们不用这种方式而是从递归入手。先定义一个递归函数f(n)表示“从起点爬到第 n 层的方法数”。现在你在第 n 层一步之前你只可能站在第 n-1 层或者第 n-2 层。因此走法数量等于f(n) f(n-1) f(n-2)边界条件先别急着套斐波那契的f(0)0。在这个具体问题是f(1)应该等于 1f(2)应该等于 2。如果按递推式倒推需要让f(0)1且f(1)1才能得到f(2)2。很多初学者在这里会困惑建议直接在递归里把边界写清楚def climb_stairs_recursive(n): if n 1: return 1 if n 2: return 2 return climb_stairs_recursive(n - 1) climb_stairs_recursive(n - 2)这样写语义很明确第 1 层只有 1 种走法第 2 层有 2 种走法11 或 2第 n 层由前两层递推而来。但有同学会担心这会不会和f(0)1的标准题解不一样没关系。不同的边界定义可以对应不同的递推写法只要你保证递归函数返回的语义是一致的最终答案就一致。把这段代码加上缓存写成动态规划def climbStairs(self, n: int) - int: if n 1: return 1 if n 2: return 2 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]你可以再优化空间因为dp[i]只依赖前两个值def climbStairs(self, n: int) - int: if n 1: return 1 if n 2: return 2 a, b 1, 2 for _ in range(3, n 1): a, b b, a b return b这一题的收获不是代码而是理解“一个递归思想可以自然转化为递推公式”。后面背包、LIS、LCS 的推导也是同一个套路只是子问题从一维变成二维抽象难度会提升。5. 背包问题从递归推到 01 背包背包问题是 LeetCode 动态规划中最高频的模型之一。你会在不少题目里看到它的影子而 LeetCode 热词里也常年有“01背包问题动态规划”、“背包 dp”、“多维背包”这些搜索。先看最基础的 01 背包问题抽象描述有一个背包最大承重是capacity。有 n 个物品第 i 个物品重量是weights[i]价值是values[i]。每个物品只能选一次问最多能装下多大价值。同样先不要背二维数组模板我们来写递归。考虑第 i 个物品时你有两个动作不选它或者选它前提是当前剩余容量还够。于是定义dfs(i, rest)表示“从第 i 个物品开始决策当前剩余容量为 rest能获得的最大价值”。它有两种选择def knapsack_dfs(weights, values, capacity): n len(weights) def dfs(i, rest): if i n: return 0 # 不选当前物品 best dfs(i 1, rest) # 选当前物品 if weights[i] rest: best max(best, values[i] dfs(i 1, rest - weights[i])) return best return dfs(0, capacity)这个递归能跑但是在总物品数和容量较大时重复计算很严重。因为dfs(i, rest)可能从不同路径被调用结果完全一样却会重复执行。优化方式是加一个(i, rest)二维缓存这就成了记忆化搜索。再看标准的二维 DPdef knapsack_dp(weights, values, capacity): n len(weights) # dp[i][rest] 表示从第 i 个物品开始决策剩余容量 rest 时的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(n - 1, -1, -1): for rest in range(capacity 1): not_take dp[i 1][rest] take 0 if weights[i] rest: take values[i] dp[i 1][rest - weights[i]] dp[i][rest] max(not_take, take) return dp[0][capacity]这里我故意选择了从后往前遍历物品。这样每一行的计算依赖的是下一行dp[i1]代码和递归版本的dfs(i, rest)保持一致非常容易对应上。实际上大部分题解用dp[i][j]表示“前 i 个物品容量为 j 的最大价值”写法略有不同但思想是一样的。你只需要掌握其中一种关键是能自己推导出来。会二维 DP 之后还有一个重要优化。观察状态转移第 i 个物品的状态只依赖上一行容量更小的状态所以可以把数组压缩成一维dp[j]def knapsack_1d(weights, values, capacity): dp [0] * (capacity 1) for w, v in zip(weights, values): for rest in range(capacity, w - 1, -1): dp[rest] max(dp[rest], dp[rest - w] v) return dp[capacity]这里最关键的一点是内层循环必须从capacity往w倒序遍历。为什么因为一维数组在更新dp[rest]时我们希望它用的是二维语义里“上一件物品”的状态。如果正序遍历dp[rest-w]可能已经在本轮被更新过那就会出现同一个物品被重复选两次这就变成完全背包问题了。背包模型在 LeetCode 中常见的变形有01 背包每个物品选 0 次或 1 次完全背包每个物品可以选无限次多维背包不仅限制重量还限制体积等分组背包每组物品最多选一个。新手没必要一上来就把所有变体都学会。先把 01 背包的递归和递推写通再遇到“目标和”、“分割等和子集”等 LeetCode 题时你会意识到它们本质上都是 01 背包换了一层皮。6. LIS 最长递增子序列从一个暴力想法开始LISLongest Increasing Subsequence最长递增子序列同样是面试高频题LeetCode 300 题就是它。题目给定一个整数数组nums找到其中最长严格递增子序列的长度。子序列不要求连续只需要保持相对顺序。这道题最常见的错误是看到“递增”下意识以为要dp[i]表示“前 i 个元素的最长递增子序列长度”。如果你这样定义转移时会发现很难表达“最后一个元素是什么”导致推导不下去。这是因为你少了必要的状态。我们可以换一种状态定义令dp[i]表示以nums[i]结尾的最长递增子序列长度。为什么这样定义因为要判断后面一个元素能否接在当前序列后面必须知道当前序列最后一个元素是谁。先用暴力一点的思路看枚举每一个位置作为子序列的结尾再往前找所有比它小的位置如果能接在那个位置后面长度就有机会加 1。写成 DP 就是def lengthOfLIS(self, nums: list[int]) - int: if not nums: return 0 n len(nums) 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[i] 1因为就算前面的所有元素都比nums[i]大单个元素本身就是一个长度为 1 的递增子序列这相当于递归里的 base case。示例验证一下nums [10, 9, 2, 5, 3, 7, 101, 18]以2结尾前面没有更小的元素dp[2] 1以5结尾前面有2比它小dp[3] dp[2] 1 2以7结尾前面有2、5、3都比它小最大能接到dp[3]后面所以dp[5] dp[3] 1 3以101结尾可以接到7后面dp[6] dp[5] 1 4。最终答案是max(dp)也就是 4。看到这里你可以回过头去问这个dp[i] max(dp[j] 1)的状态转移是怎么想到的关键就是“枚举上一个元素是谁”。既然当前元素是子序列的结尾那么上一个元素一定在它前面而且比它小。把所有可能的上一个元素都试一遍取最大值这就是最优子结构的体现。LIS 的复杂度是 O(n²)对于 LeetCode 300 的常规数据是可接受的。如果 n 很大可以用贪心加二分的写法优化到 O(n log n)但新手阶段先掌握 O(n²) 的 DP 推导更重要。7. LCS 最长公共子序列二维 DP 的入门经典如果只刷一道二维动态规划题那就刷 LCS。它在 LeetCode 上是第 1143 题最长公共子序列。题目给定两个字符串text1和text2返回它们的最长公共子序列长度。子序列可以不用连续但要保持相对顺序。因为有两个字符串递归函数通常需要两个下标分别表示“text1 的当前位置”和“text2 的当前位置”。定义dfs(i, j)表示“text1[i:]和text2[j:]的最长公共子序列长度”。递归思路分两种情况讨论如果text1[i] text2[j]那这个字符一定要配对问题变成1 dfs(i1, j1)如果不相等那就删掉text1[i]或删掉text2[j]取更长的那种方案。写成递归非常直观def lcs_recursive(text1, text2): m, n len(text1), len(text2) def dfs(i, j): if i m or j n: return 0 if text1[i] text2[j]: return 1 dfs(i 1, j 1) return max(dfs(i 1, j), dfs(i, j 1)) return dfs(0, 0)但这样会在小数据集上指数爆炸。添加缓存后就变成记忆化搜索。最常见的二维 DP 表写法如下def longestCommonSubsequence(self, text1: str, text2: str) - int: m, n len(text1), len(text2) # dp[i][j] 表示 text1[i:] 与 text2[j:] 的最长公共子序列长度 dp [[0] * (n 1) for _ in range(m 1)] for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): if text1[i] text2[j]: dp[i][j] 1 dp[i 1][j 1] else: dp[i][j] max(dp[i 1][j], dp[i][j 1]) return dp[0][0]我们来看一个示例text1 abcdetext2 ace。两个字符串末尾都走完时LCS 长度是 0。从后往前遍历当两个字符相等时加 1不相等时取删掉一端的最大值。最终答案应是 3因为公共子序列是ace。对于习惯“从左往右”写 DP 的同学注意这种写法中dp的i、j表示字符串前缀而不是从后往前。两种写法都可以但你要特别注意初始化边界。如果搞不清楚下标关系最容易出现的错误是数组越界或者在text1[i] text2[j]时写错依赖关系。判断自己是否真的懂了可以尝试把这道题 LIS 和 LCS 一起对比LCS 是普通 DPLIS 是每个位置都要枚举前面的位置背包是每个物品选或不选。它们最终都写成循环和状态数组但推导道路各不相同。能有意识地区分才是真正理解而不是背题。8. 动态规划常见问题与排查方法很多同学不是不会写 DP而是写完答案不对又不知道问题出在哪里。这里总结一份高频问题排查表。问题现象可能原因排查思路解决方案答案比预期小很多初始化的值不够大或不够合理检查dp数组的初始值尤其是求最大值/最小值时求最大值初始化为 0 或负无穷求最小值初始化为正无穷数组越界状态里访问了负数下标或超过边界的索引在转移前判断i-1、j-1、rest - weight是否越界把数组长度多开一位或在循环条件中加限制答案少 1 或多 1没有想清楚dp[i]表示“前 i 个”还是“第 i 个”在小样例下手动模拟一遍 dp 表统一语义比如用dp[i]表示前 i 个时dp[0]通常表示空集运行超时复杂度太高或者没有做记忆化检查是否递归重复计算检查是否有多余状态先加缓存再尝试改一维 DP一维滚动数组结果错误遍历顺序搞反检查内层循环是否倒序遍历01 背包从大到小遍历完全背包从小到大遍历不相等时状态漏了一种情况状态转移只枚举了一种决策检查所有可能的来源是否都写进 max/min在 LCS 中不相等时要同时考虑两个分支面对动态规划问题请一定在小数据上手动模拟。手工推一个长度为 3 或 4 的例子能帮助你快速定位到底是状态定义错了、转移方向错了还是边界条件错了。另外还有一种常见情况题目只问长度/数量面试却追问怎么输出方案。这时候你不仅需要最大长度还要记录转移来源。常见做法是开一个额外的二维数组存储每个状态从哪条路径转移过来最后从终点一步步回溯。例如 LCS 需要输出具体公共子序列时在dp[i][j]更新后记录from[i][j]最后根据记录从右下角走到左上角。9. 动态规划刷题最佳实践与工程建议聊完了推导方法再围绕“怎么刷题”分享几条更可操作的建议。9.1 审题先确认能不能用 DP看到一道题别急着定位到某种 DP 模板。先问自己三个问题当前问题能不能拆成子问题子问题是否在后续计算中被重复使用子问题的最优解能不能组合出原问题的最优解如果三条都满足再进入状态定义环节。如果不满足比如题目要求输出“所有方案”那它往往更适合用回溯而不是 DP。9.2 写题时先让程序能跑再优化第一次做题时直接写暴力递归是完全可以接受的。等递归跑通了再判断性能是否满足要求。LeetCode 前面几题可能暴力也能过因为测试样例比较小如果超时再加记忆化。这是一个“由正确到高效”的过程。在实际编码面试中面试官其实更看重你能不能先给出可运行的正确方案再逐步优化。一上来就写一维滚动数组反而容易因为边界错误浪费大量时间。9.3 用固定套路写解题笔记LeetCode 刷题容易陷入“刷了就忘”的循环。建议每道动态规划题都固定记录四部分1. 状态定义dp[i] / dp[i][j] 表示什么 2. 初始化dp 的初值是什么为什么 3. 转移方程当前状态可能从哪些状态转移过来 4. 遍历顺序从左到右还是从右到左外层循环需要几个变量这四点正好就是动态规划题的完整骨架。当你能用自己的话把这四点写清楚再去做同类题时会发现识别速度明显变快。9.4 同类题集中训练不要一道题刷完就换题型动态规划有很多子类型线性 DP、区间 DP、背包 DP、状态压缩 DP、树形 DP。如果你今天是背包明天是区间 DP后天是数位 DP跨度太大很难建立手感。更有效的做法是连续一周只刷一类题。比如先按“01 背包 - 分割等和子集 - 目标和 - 最后一块石头的重量 II”的顺序练习。你会发现它们的状态定义都很相似核心都是“每个物品选或不选”。这种集中训练带来的“题感”比刷十道互不相关的题更好。9.5 不要迷信奇技淫巧先掌握两个核心思路如果你时间有限至少掌握两种状态组织思路dp[i]表示“以第 i 个元素结尾”的某个值。常见于 LIS、最大子数组和等dp[i][j]表示“前 i 个物品在限制 j 下的最优值”或“两个字符串 i 位置和 j 位置匹配时的最优值”。常见于背包、LCS、编辑距离等。有了这两个状态组织方式你会发现自己能看懂题解的数量一下子变多了。后续再看更复杂的区间 DP再在这个基础上增加维度思路会顺很多。10. 总结与后续学习方向这篇文章想解决的从来不只是让你会做某道题而是帮你建立一个新的反应链路读到一道动态规划题先尝试把问题“翻译”成递归函数再通过记忆化搜索降低复杂度最后改成递推 DP。用这个方法推爬楼梯、推 01 背包、推 LIS、推 LCS你都会发现状态转移方程是靠自己的逻辑走出来的不需要硬背。回到“小白怎么刷 LeetCode”这个长期主题动态规划需要反复练习才能内化。如果这篇你现在读完觉得顺利接下来建议按这个顺序做几道题验证自己LeetCode 70爬楼梯LeetCode 198打家劫舍LeetCode 416分割等和子集LeetCode 300最长递增子序列LeetCode 1143最长公共子序列。这些题覆盖了线性 DP 和背包思想的常见变体。做的时候不要急于看题解哪怕花一个小时在草稿纸上画状态也比三分钟抄答案更有收获。DP 不怕慢就怕你不愿意推导。把状态转移方程当成结论来背是你和动态规划之间最大的隔阂。从今天开始碰到一道 DP 题先问自己一句话如果用递归我该怎么定义这个函数答案写下后你已经离最优雅的递推式不远了。建议收藏本文下次刷题卡住时再回看这一套推导方法。