打开 LeetCode 刷题列表动态规划专题往往是劝退新手的第一道高墙。“dp[i] max(dp[i-1] nums[i], nums[i])”“if s[i] t[j]: dp[i][j] dp[i-1][j-1] 1”……满屏的状态转移方程让人头皮发麻于是很多人选择死记硬背结果题目一变形立刻歇菜。这篇文章不打算让你背任何一个方程。我会带你从最朴素的递归开始一步步通过“暴力递归 → 记忆化搜索 → 迭代动态规划”的路线亲手推导出动态规划解法。再用背包、LIS最长递增子序列、LCS最长公共子序列三道经典题把这条推导链路走通。读完你应该具备一种能力遇到一道新 DP 题至少知道怎么下手而不是先去搜题解。1. 动态规划到底是什么1.1 用大白话理解动态规划动态规划Dynamic ProgrammingDP听名字很高级核心思想其实就一句话把一个大问题拆成若干有重叠的小问题先解决小问题再组合出大问题的答案。举个例子你想计算自己从 1 楼爬到 10 楼有多少种走法每次可以跨 1 级或 2 级台阶。你不需要真的去枚举每条路径你只需要知道到第 9 楼的走法数加上最后跨 1 级到第 8 楼的走法数加上最后跨 2 级。所以到第 10 楼的走法 到第 9 楼的走法 到第 8 楼的走法这就是一个典型的递推关系你不需要关系中间每一层具体怎么走的只要知道数量。动态规划做的就是类似的事情利用子问题的答案递推得到父问题的答案。1.2 什么题目适合用动态规划判断一道题能不能用 DP一般看两个特征最优子结构大问题的最优解可以由子问题的最优解组合而成。重叠子问题在递归求解过程中同一个子问题会被反复计算多次。这两个特征同时出现时动态规划通常能派上用场。比如求最短路径从 A 到 D 的最短路如果必经 B那么 A 到 D 的最短路可以拆成 A 到 B 的最短路加上 B 到 D 的最短路。这里既有子问题又会反复计算中间节点的最短路符合 DP 的特征。1.3 为什么不要背状态转移方程状态转移方程是 DP 解题的“结果”不是“原因”。它描述的是“子问题之间如何递推”但这个关系本身是从题目逻辑里推导出来的。如果你跳过分析过程直接背“dp[i] max(dp[i-1], dp[i-2] nums[i])”那么当题目变成“不能取相邻元素”、“环形数组”、“需要输出具体方案”时方程稍微一变你就认不出来了。正确的学习路径是审题 → 定义递归函数描述子问题 → 写暴力递归 → 加缓存记忆化搜索 → 把递归改成递推 → 观察能否压缩空间这条路径每一步都有章可循不需要灵光一现也不依赖背诵。2. 环境准备与刷题工具动态规划是算法题对运行环境要求不高。你只需要满足下面条件就可以开始任意一种编程语言的基础语法能力本文示例用 Python 和 Java两版逻辑一致。一个能运行代码的环境本地 IDEIDEA、PyCharm、VS Code或在线代码运行平台都可以。如果使用 LeetCode建议直接在网页编辑器里写方便提交验证。本文所有代码示例都按“核心函数 调用示例”的方式给出。Python 示例使用 3.8 版本Java 示例使用 JDK 8 版本即可运行不需要额外引入第三方依赖。3. 核心思想从递归到 DP 的三步推导法为了让你彻底扔掉“背方程”的拐杖我把动态规划的思考过程固定成三步后面所有例题都按这个流程走。3.1 第一步定义递归函数拿到题目后先不要想“dp 数组怎么开”而是问自己一个问题我能不能用一个递归函数 f(n) 来描述我要求的答案f(n) 的输入是什么f(n) 的输出是什么f(n) 和更小的 f(n-1)、f(n-2) 有什么关系这一步要求你具备“把问题规模缩小”的直觉。比如“爬楼梯”问题f(n) 表示爬到第 n 阶有多少种方法比如“最长递增子序列”问题可以定义 f(i) 表示以第 i 个元素结尾的最长递增子序列长度。定义好递归函数后马上写递归出口base case然后尝试写出递归调用关系。这一步不追求性能只要逻辑对就行。3.2 第二步加缓存变成记忆化搜索递归写出来之后你会发现很多子问题被重复求解。比如 f(10) 会调用 f(9) 和 f(8)f(9) 又会调用 f(8) 和 f(7)这里 f(8) 被算了两次。解决办法很简单用一个数组或哈希表把已经算过的 f(k) 存起来下次再需要 f(k) 时直接返回缓存结果。这一步的代码改动很小但能把指数级的时间复杂度降到多项式级别。此时你已经得到了一个“能用但可能栈溢出”的递归版本。3.3 第三步改成迭代递推并考虑空间优化递归是“自顶向下”从大问题一路拆到小问题迭代是“自底向上”先算最小的子问题再逐步组合出大问题。迭代递推的好处是避免递归调用栈过深。代码通常更简洁。容易进一步做空间压缩。改写方式也很固定把递归函数的参数映射成数组下标把递归出口映射成数组初始值把递归调用关系映射成循环里的状态转移。如果是二维 DP则用二维数组如果递推时只用到了前一行或前一个值还可以用滚动数组优化空间。3.4 一个立刻能上手的例子斐波那契数列我们拿最经典的斐波那契数列串一遍三步法。题目求斐波那契数列的第 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)第二步加缓存。def fib(n, memoNone): if memo is None: memo {} if n 1: return n if n in memo: return memo[n] memo[n] fib(n-1, memo) fib(n-2, memo) return memo[n]第三步改成迭代递推。def fib(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[i] 只依赖 dp[i-1] 和 dp[i-2]所以可以把一维数组再压缩成两个变量def fib(n): if n 1: return n prev2, prev1 0, 1 for _ in range(2, n 1): cur prev1 prev2 prev2 prev1 prev1 cur return prev1以上就是动态规划完整推导链路的缩影。很多初学者直接看第三步的代码会觉得“这不就是把数学公式翻译一下吗”从而误以为 DP 就是找递推公式。实际上真正的难点在第一、二步你能不能自然地从题目描述中抽象出递归关系。4. 实战案例从递归推导三个经典动态规划模型接下来我们完整走三个最常考的 DP 模型0-1 背包、最长递增子序列LIS、最长公共子序列LCS。每一题我都严格按照“递归 → 记忆化 → 迭代递推”的顺序展开你可以亲手敲一遍感受 DP 是如何“长”出来的。4.1 案例一0-1 背包问题4.1.1 题目描述有 N 件物品和一个容量为 W 的背包。每件物品有重量 wt[i] 和价值 val[i]每种物品只能选择放入或不放入一次求能装入背包的最大总价值。经典的 0-1 背包问题。为什么叫“0-1”因为每件物品只有两种状态取1或不取0。4.1.2 递归定义直接想 dp 数组可能有点抽象我们先定义递归函数f(i, c) 在前 i 件物品中做选择背包剩余容量为 c 时能获得的最大价值对于第 i 件物品我们有两种选择不选问题变成 f(i-1, c)。选前提是 c wt[i]问题变成 val[i] f(i-1, c - wt[i])。所以递归关系是f(i, c) max( f(i-1, c), val[i] f(i-1, c - wt[i]) )递归出口有两个没有物品可选时价值为 0即 i 0 时返回 0背包容量不足时不能选当前物品。用 Python 写暴力递归如下def knapsack_recursive(wt, val, i, c): # 没有物品可选或容量为负 if i 0 or c 0: return 0 # 当前物品放不下只能跳过 if wt[i] c: return knapsack_recursive(wt, val, i-1, c) # 不选 vs 选取较大值 no_take knapsack_recursive(wt, val, i-1, c) take val[i] knapsack_recursive(wt, val, i-1, c - wt[i]) return max(no_take, take) wt [2, 3, 4, 5] val [3, 4, 5, 6] n len(wt) capacity 8 print(knapsack_recursive(wt, val, n-1, capacity))运行结果10解释选择物品 0重量 2价值 3、物品 1重量 3价值 4、物品 3重量 5价值 6总重量 10 超过容量 8。实际上最优方案是物品 0 物品 1 物品 2 重量 9 也超过。再调整物品 0 物品 2 重量 6价值 8物品 1 物品 3 重量 8价值 10。所以最大价值是 10。这个递归版本在 N 和 W 稍大时会非常慢因为递归树是二分支的时间复杂度接近指数级。我们把递归过程画出来就能看到大量重复计算比如 f(2, 5) 可能在不同分支里反复出现。4.1.3 加缓存记忆化搜索加一个 memo 二维数组记录每个 (i, c) 的结果。因为 i 的范围是 0 到 N-1c 的范围是 0 到 W所以开一个(N) x (W1)的数组就够了。用 -1 表示尚未计算。def knapsack_memo(wt, val, W): n len(wt) memo [[-1] * (W 1) for _ in range(n)] def dfs(i, c): if i 0 or c 0: return 0 if memo[i][c] ! -1: return memo[i][c] if wt[i] c: memo[i][c] dfs(i-1, c) else: no_take dfs(i-1, c) take val[i] dfs(i-1, c - wt[i]) memo[i][c] max(no_take, take) return memo[i][c] return dfs(n-1, W) wt [2, 3, 4, 5] val [3, 4, 5, 6] print(knapsack_memo(wt, val, 8))运行结果同样是10这个版本的时间复杂度已经降到 O(NW)空间复杂度也是 O(NW)。递归仍然存在栈深度风险但对常规测试数据已经可用了。4.1.4 改写成迭代 DP递归是“从后往前”思考迭代 DP 可以“从前往后”填表。我们定义 dp[i][c] 表示“从前 i 件物品中选容量为 c 时能获得的最大价值”。注意这里 i 从 1 开始计数方便留出 i0 表示“没有物品”。状态转移不选第 i 件物品dp[i][c] dp[i-1][c]选第 i 件物品dp[i][c] dp[i-1][c-wt[i-1]] val[i-1]前提 c wt[i-1]。代码如下def knapsack_dp(wt, val, W): n len(wt) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for c in range(1, W 1): if wt[i-1] c: dp[i][c] dp[i-1][c] else: dp[i][c] max(dp[i-1][c], dp[i-1][c-wt[i-1]] val[i-1]) return dp[n][W] wt [2, 3, 4, 5] val [3, 4, 5, 6] print(knapsack_dp(wt, val, 8))运行结果104.1.5 一维数组空间优化观察状态转移方程dp[i][c] 只依赖 dp[i-1][c] 和 dp[i-1][c-wt[i-1]]也就是“上一行”的数据。因此我们不需要保留完整的二维表只需要一行长度为 W1 的数组每轮从后往前更新即可。为什么要从后往前因为 dp[c] 更新时用到的是“上一轮较小容量 c-wt[i-1] 的值”。如果从前往后更新dp[c-wt[i-1]] 可能已经被本轮覆盖导致同一件物品被重复放入那就变成完全背包了。def knapsack_dp_1d(wt, val, W): n len(wt) dp [0] * (W 1) for i in range(n): # 逆序遍历容量防止物品被重复选择 for c in range(W, wt[i] - 1, -1): dp[c] max(dp[c], dp[c - wt[i]] val[i]) return dp[W] wt [2, 3, 4, 5] val [3, 4, 5, 6] print(knapsack_dp_1d(wt, val, 8))输出结果依然是10对照四个版本的代码你能清楚地看到“递归定义 → 缓存 → 递推 → 空间优化”这条演变路径。面试时如果要求输出最优方案的具体物品就需要回退到二维 DP额外记录选择路径。4.2 案例二最长递增子序列LIS4.2.1 题目描述给定一个整数数组 nums找到其中最长严格递增子序列的长度。子序列不要求连续但要保持原数组中的相对顺序。例如nums [10, 9, 2, 5, 3, 7, 101, 18] 最长递增子序列是 [2, 3, 7, 101]长度为 44.2.2 递归定义很多同学第一次接触 LIS 时会想当然地定义 f(i) 为“前 i 个元素的最长递增子序列长度”。但这个定义有问题你无法从前 i-1 个元素的结果直接推导出第 i 个元素加入后的结果因为你不知道前 i-1 个元素的最长递增子序列末尾元素是谁也就无法判断第 i 个元素能不能接在后面。正确的做法是定义f(i) 以 nums[i] 结尾的最长递增子序列长度为什么这样定义因为“以某个元素结尾”把子序列的结束位置固定住了这样后续状态转移时我们只要比较“当前元素能否接在某个前面的元素后面”即可。递归关系初始化 f(i) 1因为单个元素自身可以构成长度为 1 的递增子序列。对于每个 j i如果 nums[j] nums[i]那么 f(i) 可以考虑从 f(j) 1 转移过来。对应的递归思路可以写成f(i) 1 max( f(j) )其中 j i 且 nums[j] nums[i]如果没有任何满足条件的 j那么 f(i) 1。4.2.3 暴力递归到记忆化搜索用 Python 写一个自顶向下的版本。递归函数 dfs(i) 表示“以 nums[i] 结尾的最长递增子序列长度”。def length_of_lis_memo(nums): n len(nums) memo [0] * n def dfs(i): if memo[i] ! 0: return memo[i] best 1 for j in range(i): if nums[j] nums[i]: best max(best, dfs(j) 1) memo[i] best return best ans 0 for i in range(n): ans max(ans, dfs(i)) return ans nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_memo(nums))运行结果4这段代码里 dfs(i) 会递归地去找前面所有比 nums[i] 小的元素把它们的 LIS 长度算出来再加 1。4.2.4 迭代 DP 版本把自顶向下的递归改成自底向上的双重循环def length_of_lis_dp(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) nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_dp(nums))运行结果4这个版本的时间复杂度是 O(n²)空间复杂度是 O(n)。4.2.5 进阶贪心 二分优化到 O(n log n)LIS 还有一个非常经典的优化思路用tails数组维护“长度为 k 的递增子序列的最小末尾元素”。遍历每个元素时在 tails 中二分查找第一个不小于当前元素的位置并替换如果当前元素比 tails 中所有元素都大就追加到末尾。import bisect def length_of_lis_binary(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) nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_binary(nums))结果仍然是4注意tails 数组本身并不一定是真实的 LIS 序列它只是用来辅助计算长度的。这个方法适合只求长度、不要求输出具体序列的场景。4.3 案例三最长公共子序列LCS4.3.1 题目描述给定两个字符串 text1 和 text2返回两个字符串的最长公共子序列的长度。子序列可以不连续但相对顺序必须一致。例如text1 abcde text2 ace 最长公共子序列是 ace长度为 3如果两个字符串没有公共子序列返回 0。4.3.2 递归定义LCS 问题是一个典型的二维 DP。我们定义递归函数f(i, j) text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度其中 i 和 j 可以取 0表示空字符串。递归关系分两种情况如果 text1[i-1] text2[j-1]说明当前两个字符可以匹配那么f(i, j) f(i-1, j-1) 1如果不相等则当前字符不可能同时出现在公共子序列中只能选择丢弃 text1 的最后一个字符或者丢弃 text2 的最后一个字符f(i, j) max( f(i-1, j), f(i, j-1) )递归出口f(0, j) 0 f(i, 0) 0因为空字符串和任何字符串都没有公共字符。4.3.3 暴力递归到记忆化搜索先写一个自顶向下的递归版本def lcs_memo(text1, text2): m, n len(text1), len(text2) memo [[-1] * (n 1) for _ in range(m 1)] def dfs(i, j): if i 0 or j 0: return 0 if memo[i][j] ! -1: return memo[i][j] if text1[i-1] text2[j-1]: memo[i][j] dfs(i-1, j-1) 1 else: memo[i][j] max(dfs(i-1, j), dfs(i, j-1)) return memo[i][j] return dfs(m, n) print(lcs_memo(abcde, ace))运行结果3这里 memo[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。注意递归函数与数组下标从 1 开始和字符串下标差一位。4.3.4 迭代 DP 版本把递归改成双层循环自底向上填表。dp[i][j] 的含义与 memo[i][j] 一致。def lcs_dp(text1, text2): m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i-1] text2[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] print(lcs_dp(abcde, ace))运行结果34.3.5 空间优化LCS 的二维表也可以压缩成一行因为 dp[i][j] 更新时依赖三个位置dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。如果只保留上一行的一维数组我们需要用一个临时变量记录 dp[i-1][j-1]对应左上角的值。def lcs_dp_1d(text1, text2): m, n len(text1), len(text2) dp [0] * (n 1) for i in range(1, m 1): prev 0 # 相当于 dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 保存当前 dp[j]它是下一轮循环的“上一行左上角” if text1[i-1] text2[j-1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j-1]) prev temp return dp[n] print(lcs_dp_1d(abcde, ace))结果还是3这个压缩过程理解起来比一维背包略复杂核心是搞清楚prev变量保存的是哪个历史状态。建议你先跑通二维版本再对照二维表中“当前行覆盖上一行”的过程来理解一维版本不要一上来直接硬啃。5. 动态规划学习中的常见问题与排查思路很多新手自己做 DP 题报错时第一反应是去改代码但其实问题出在“对子问题的定义”上。我整理了刷题时最容易遇到的几类问题帮你对症下药。问题现象常见原因解决思路暴力递归超时存在大量重叠子问题没有加缓存先加 memo 数组改成记忆化搜索递归栈溢出递归深度过大改成自底向上的迭代 DP结果比答案小子问题定义不完整丢失了关键信息检查状态定义是否包含足够信息比如 LIS 需要固定“以当前元素结尾”结果比答案大状态转移时错误地重复使用了某个元素检查是否需要对容量、下标、选择次数做限制比如 0-1 背包需要逆序更新一维数组一维空间优化后结果错误更新方向错误导致状态被覆盖回退到二维版本逐个打印 dp 表排查边界条件为空数组/空串时出错没有处理 base case先把 n0、m0 等极端输入跑一遍5.1 如何定位递归中的重复计算如果你不确定自己的递归是否存在大量重复计算可以在递归函数里加一个计数器或者打印递归调用参数。比如def dfs(i, c): print(fcall dfs({i}, {c})) ...如果看到相同的 (i, c) 反复出现就说明存在重叠子问题有必要使用记忆化搜索。5.2 状态定义不清晰导致的玄学报错这是 DP 新手最隐蔽的坑。以 LIS 为例如果你把 f(i) 定义成“前 i 个元素的最长递增子序列长度”那么当 nums[i] 很小但前面的最长递增子序列末尾很大时你是无法判断能不能把 nums[i] 接上去的。这会导致递推关系无法建立或者结果错误。遇到这种情况解决问题的关键不是改代码而是回头重新定义状态。一个常用的技巧是增加约束条件让子问题之间能够“衔接”。LIS 中“以第 i 个元素结尾”就是一种常见的约束。5.3 对着题解能看懂自己写就卡住这是正常的学习曲线。建议你不要只看题解代码而是找一道中等难度 DP 题按照“递归定义 → 暴力递归 → 记忆化 → 迭代 DP”的顺序自己从头到尾完整推一遍。这个过程会强迫你把“状态怎么转移”讲清楚而不是被动接受现成的 dp 方程。6. 动态规划的最佳实践与刷题建议6.1 先画递归树再写代码拿到一道 DP 题不要急着敲键盘。在草稿纸上画出小规模输入的递归树标注哪些节点被重复计算。这个动作能帮你同时验证“子问题是否重叠”和“递归关系是否正确”。比如爬楼梯问题n5 的递归树中 f(3) 会出现两次f(2) 会出现三次画出来之后你自然理解为什么要记忆化。6.2 状态定义口诀最后一步看什么状态就存什么如果你不知道 dp 数组的每个维度代表什么可以问自己一个终极问题当我只差最后一步就能得到答案时我需要知道哪些信息背包问题需要知道还剩多少容量以及已经处理到第几件物品所以状态是 f(i, c)。LIS需要知道当前递增子序列以哪个元素结尾所以状态是 f(i)。编辑距离需要知道两个字符串分别处理到哪个位置所以状态是 f(i, j)。这个“最后一步分析法”有时候比生搬套路更有效建议你在做题时反复练习。6.3 用一维还是二维取决于状态依赖关系很多同学会陷入“必须写出空间最优解”的执念。实战中建议你先用最直观的二维 DP 写出正确版本提交通过后再考虑能否用滚动数组或一维数组优化优化前用注释列出一维数组更新时可能覆盖的旧值再动手改代码。空间优化是锦上添花不是雪中送炭。面试时如果时间紧张先写出正确解比写出最优解更重要。6.4 刷题顺序建议如果你的动态规划还处于入门阶段不推荐直接挑战困难题。可以参考下面这个难度递增路径爬楼梯、斐波那契数列体会“递推 空间压缩”不同路径、最小路径和体验二维 DP 表格怎么填最长递增子序列、最长公共子序列练习子序列类模型0-1 背包、完全背包掌握最经典的背包模型打家劫舍系列、买卖股票系列练习状态机式 DP区间 DP、树形 DP进阶方向按需学习。每一步都要保证自己能用“递归 → 记忆化 → 递推”的流程独立推导出来再进入下一类题。6.5 关于代码的工程习惯刷题代码和生产代码要求不同但以下习惯值得保持函数命名清晰让别人一眼知道这个函数在算什么状态数组的语义用注释说明例如dp[c]表示“容量为 c 时的最大价值”把 base case 单独写清楚不要藏在循环条件里写完代码后用一组边界数据自测空输入、最小输入、最大输入、相等元素输入。如果你在本地 IDE 中练习还可以自己写一个简单的测试函数批量断言结果便于后续回归def test_lis(): assert length_of_lis_dp([10, 9, 2, 5, 3, 7, 101, 18]) 4 assert length_of_lis_dp([0]) 1 assert length_of_lis_dp([]) 0 print(all test cases passed) test_lis()7. 总结动态规划并不可怕可怕的是用背题的方式去学它。这篇文章的核心观点是状态转移方程不是背出来的而是从递归定义里一步步推出来的。我们完整走通了三条推导路径0-1 背包从 f(i, c) 的递归定义出发经过记忆化搜索改写成二维递推最终压缩成一维逆序更新最长递增子序列从 f(i) 表示“以 nums[i] 结尾”的递归定义出发推导出 O(n²) 的 DP再介绍了 O(n log n) 的二分优化最长公共子序列从二维递归 f(i, j) 出发对照字符相等和不相等两种情况推导出二维填表逻辑再分析了空间压缩的细节。如果你能把这三种模型的推导过程自己复现一遍再去做 LeetCode 上的同类变体题比如跳跃游戏、编辑距离、零钱兑换会发现这些题远没有想象中难。关键在于先想清楚一件事我正在求解的子问题是什么它和我已经解决过的更小子问题之间是什么关系想清楚这个代码只是顺手的事。拿一道题练手吧LeetCode 300 最长递增子序列或者 LeetCode 1143 最长公共子序列先别看题解按文中的三步法自己推一遍。遇到卡壳的地方回来对照文章的推导过程看看自己是在状态定义、递归关系、还是边界处理上出了问题。多推几道你就能慢慢建立属于自己的动态规划直觉了。 告别死记硬背：从递归到动态规划的三步推导法
打开 LeetCode 刷题列表动态规划专题往往是劝退新手的第一道高墙。“dp[i] max(dp[i-1] nums[i], nums[i])”“if s[i] t[j]: dp[i][j] dp[i-1][j-1] 1”……满屏的状态转移方程让人头皮发麻于是很多人选择死记硬背结果题目一变形立刻歇菜。这篇文章不打算让你背任何一个方程。我会带你从最朴素的递归开始一步步通过“暴力递归 → 记忆化搜索 → 迭代动态规划”的路线亲手推导出动态规划解法。再用背包、LIS最长递增子序列、LCS最长公共子序列三道经典题把这条推导链路走通。读完你应该具备一种能力遇到一道新 DP 题至少知道怎么下手而不是先去搜题解。1. 动态规划到底是什么1.1 用大白话理解动态规划动态规划Dynamic ProgrammingDP听名字很高级核心思想其实就一句话把一个大问题拆成若干有重叠的小问题先解决小问题再组合出大问题的答案。举个例子你想计算自己从 1 楼爬到 10 楼有多少种走法每次可以跨 1 级或 2 级台阶。你不需要真的去枚举每条路径你只需要知道到第 9 楼的走法数加上最后跨 1 级到第 8 楼的走法数加上最后跨 2 级。所以到第 10 楼的走法 到第 9 楼的走法 到第 8 楼的走法这就是一个典型的递推关系你不需要关系中间每一层具体怎么走的只要知道数量。动态规划做的就是类似的事情利用子问题的答案递推得到父问题的答案。1.2 什么题目适合用动态规划判断一道题能不能用 DP一般看两个特征最优子结构大问题的最优解可以由子问题的最优解组合而成。重叠子问题在递归求解过程中同一个子问题会被反复计算多次。这两个特征同时出现时动态规划通常能派上用场。比如求最短路径从 A 到 D 的最短路如果必经 B那么 A 到 D 的最短路可以拆成 A 到 B 的最短路加上 B 到 D 的最短路。这里既有子问题又会反复计算中间节点的最短路符合 DP 的特征。1.3 为什么不要背状态转移方程状态转移方程是 DP 解题的“结果”不是“原因”。它描述的是“子问题之间如何递推”但这个关系本身是从题目逻辑里推导出来的。如果你跳过分析过程直接背“dp[i] max(dp[i-1], dp[i-2] nums[i])”那么当题目变成“不能取相邻元素”、“环形数组”、“需要输出具体方案”时方程稍微一变你就认不出来了。正确的学习路径是审题 → 定义递归函数描述子问题 → 写暴力递归 → 加缓存记忆化搜索 → 把递归改成递推 → 观察能否压缩空间这条路径每一步都有章可循不需要灵光一现也不依赖背诵。2. 环境准备与刷题工具动态规划是算法题对运行环境要求不高。你只需要满足下面条件就可以开始任意一种编程语言的基础语法能力本文示例用 Python 和 Java两版逻辑一致。一个能运行代码的环境本地 IDEIDEA、PyCharm、VS Code或在线代码运行平台都可以。如果使用 LeetCode建议直接在网页编辑器里写方便提交验证。本文所有代码示例都按“核心函数 调用示例”的方式给出。Python 示例使用 3.8 版本Java 示例使用 JDK 8 版本即可运行不需要额外引入第三方依赖。3. 核心思想从递归到 DP 的三步推导法为了让你彻底扔掉“背方程”的拐杖我把动态规划的思考过程固定成三步后面所有例题都按这个流程走。3.1 第一步定义递归函数拿到题目后先不要想“dp 数组怎么开”而是问自己一个问题我能不能用一个递归函数 f(n) 来描述我要求的答案f(n) 的输入是什么f(n) 的输出是什么f(n) 和更小的 f(n-1)、f(n-2) 有什么关系这一步要求你具备“把问题规模缩小”的直觉。比如“爬楼梯”问题f(n) 表示爬到第 n 阶有多少种方法比如“最长递增子序列”问题可以定义 f(i) 表示以第 i 个元素结尾的最长递增子序列长度。定义好递归函数后马上写递归出口base case然后尝试写出递归调用关系。这一步不追求性能只要逻辑对就行。3.2 第二步加缓存变成记忆化搜索递归写出来之后你会发现很多子问题被重复求解。比如 f(10) 会调用 f(9) 和 f(8)f(9) 又会调用 f(8) 和 f(7)这里 f(8) 被算了两次。解决办法很简单用一个数组或哈希表把已经算过的 f(k) 存起来下次再需要 f(k) 时直接返回缓存结果。这一步的代码改动很小但能把指数级的时间复杂度降到多项式级别。此时你已经得到了一个“能用但可能栈溢出”的递归版本。3.3 第三步改成迭代递推并考虑空间优化递归是“自顶向下”从大问题一路拆到小问题迭代是“自底向上”先算最小的子问题再逐步组合出大问题。迭代递推的好处是避免递归调用栈过深。代码通常更简洁。容易进一步做空间压缩。改写方式也很固定把递归函数的参数映射成数组下标把递归出口映射成数组初始值把递归调用关系映射成循环里的状态转移。如果是二维 DP则用二维数组如果递推时只用到了前一行或前一个值还可以用滚动数组优化空间。3.4 一个立刻能上手的例子斐波那契数列我们拿最经典的斐波那契数列串一遍三步法。题目求斐波那契数列的第 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)第二步加缓存。def fib(n, memoNone): if memo is None: memo {} if n 1: return n if n in memo: return memo[n] memo[n] fib(n-1, memo) fib(n-2, memo) return memo[n]第三步改成迭代递推。def fib(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[i] 只依赖 dp[i-1] 和 dp[i-2]所以可以把一维数组再压缩成两个变量def fib(n): if n 1: return n prev2, prev1 0, 1 for _ in range(2, n 1): cur prev1 prev2 prev2 prev1 prev1 cur return prev1以上就是动态规划完整推导链路的缩影。很多初学者直接看第三步的代码会觉得“这不就是把数学公式翻译一下吗”从而误以为 DP 就是找递推公式。实际上真正的难点在第一、二步你能不能自然地从题目描述中抽象出递归关系。4. 实战案例从递归推导三个经典动态规划模型接下来我们完整走三个最常考的 DP 模型0-1 背包、最长递增子序列LIS、最长公共子序列LCS。每一题我都严格按照“递归 → 记忆化 → 迭代递推”的顺序展开你可以亲手敲一遍感受 DP 是如何“长”出来的。4.1 案例一0-1 背包问题4.1.1 题目描述有 N 件物品和一个容量为 W 的背包。每件物品有重量 wt[i] 和价值 val[i]每种物品只能选择放入或不放入一次求能装入背包的最大总价值。经典的 0-1 背包问题。为什么叫“0-1”因为每件物品只有两种状态取1或不取0。4.1.2 递归定义直接想 dp 数组可能有点抽象我们先定义递归函数f(i, c) 在前 i 件物品中做选择背包剩余容量为 c 时能获得的最大价值对于第 i 件物品我们有两种选择不选问题变成 f(i-1, c)。选前提是 c wt[i]问题变成 val[i] f(i-1, c - wt[i])。所以递归关系是f(i, c) max( f(i-1, c), val[i] f(i-1, c - wt[i]) )递归出口有两个没有物品可选时价值为 0即 i 0 时返回 0背包容量不足时不能选当前物品。用 Python 写暴力递归如下def knapsack_recursive(wt, val, i, c): # 没有物品可选或容量为负 if i 0 or c 0: return 0 # 当前物品放不下只能跳过 if wt[i] c: return knapsack_recursive(wt, val, i-1, c) # 不选 vs 选取较大值 no_take knapsack_recursive(wt, val, i-1, c) take val[i] knapsack_recursive(wt, val, i-1, c - wt[i]) return max(no_take, take) wt [2, 3, 4, 5] val [3, 4, 5, 6] n len(wt) capacity 8 print(knapsack_recursive(wt, val, n-1, capacity))运行结果10解释选择物品 0重量 2价值 3、物品 1重量 3价值 4、物品 3重量 5价值 6总重量 10 超过容量 8。实际上最优方案是物品 0 物品 1 物品 2 重量 9 也超过。再调整物品 0 物品 2 重量 6价值 8物品 1 物品 3 重量 8价值 10。所以最大价值是 10。这个递归版本在 N 和 W 稍大时会非常慢因为递归树是二分支的时间复杂度接近指数级。我们把递归过程画出来就能看到大量重复计算比如 f(2, 5) 可能在不同分支里反复出现。4.1.3 加缓存记忆化搜索加一个 memo 二维数组记录每个 (i, c) 的结果。因为 i 的范围是 0 到 N-1c 的范围是 0 到 W所以开一个(N) x (W1)的数组就够了。用 -1 表示尚未计算。def knapsack_memo(wt, val, W): n len(wt) memo [[-1] * (W 1) for _ in range(n)] def dfs(i, c): if i 0 or c 0: return 0 if memo[i][c] ! -1: return memo[i][c] if wt[i] c: memo[i][c] dfs(i-1, c) else: no_take dfs(i-1, c) take val[i] dfs(i-1, c - wt[i]) memo[i][c] max(no_take, take) return memo[i][c] return dfs(n-1, W) wt [2, 3, 4, 5] val [3, 4, 5, 6] print(knapsack_memo(wt, val, 8))运行结果同样是10这个版本的时间复杂度已经降到 O(NW)空间复杂度也是 O(NW)。递归仍然存在栈深度风险但对常规测试数据已经可用了。4.1.4 改写成迭代 DP递归是“从后往前”思考迭代 DP 可以“从前往后”填表。我们定义 dp[i][c] 表示“从前 i 件物品中选容量为 c 时能获得的最大价值”。注意这里 i 从 1 开始计数方便留出 i0 表示“没有物品”。状态转移不选第 i 件物品dp[i][c] dp[i-1][c]选第 i 件物品dp[i][c] dp[i-1][c-wt[i-1]] val[i-1]前提 c wt[i-1]。代码如下def knapsack_dp(wt, val, W): n len(wt) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for c in range(1, W 1): if wt[i-1] c: dp[i][c] dp[i-1][c] else: dp[i][c] max(dp[i-1][c], dp[i-1][c-wt[i-1]] val[i-1]) return dp[n][W] wt [2, 3, 4, 5] val [3, 4, 5, 6] print(knapsack_dp(wt, val, 8))运行结果104.1.5 一维数组空间优化观察状态转移方程dp[i][c] 只依赖 dp[i-1][c] 和 dp[i-1][c-wt[i-1]]也就是“上一行”的数据。因此我们不需要保留完整的二维表只需要一行长度为 W1 的数组每轮从后往前更新即可。为什么要从后往前因为 dp[c] 更新时用到的是“上一轮较小容量 c-wt[i-1] 的值”。如果从前往后更新dp[c-wt[i-1]] 可能已经被本轮覆盖导致同一件物品被重复放入那就变成完全背包了。def knapsack_dp_1d(wt, val, W): n len(wt) dp [0] * (W 1) for i in range(n): # 逆序遍历容量防止物品被重复选择 for c in range(W, wt[i] - 1, -1): dp[c] max(dp[c], dp[c - wt[i]] val[i]) return dp[W] wt [2, 3, 4, 5] val [3, 4, 5, 6] print(knapsack_dp_1d(wt, val, 8))输出结果依然是10对照四个版本的代码你能清楚地看到“递归定义 → 缓存 → 递推 → 空间优化”这条演变路径。面试时如果要求输出最优方案的具体物品就需要回退到二维 DP额外记录选择路径。4.2 案例二最长递增子序列LIS4.2.1 题目描述给定一个整数数组 nums找到其中最长严格递增子序列的长度。子序列不要求连续但要保持原数组中的相对顺序。例如nums [10, 9, 2, 5, 3, 7, 101, 18] 最长递增子序列是 [2, 3, 7, 101]长度为 44.2.2 递归定义很多同学第一次接触 LIS 时会想当然地定义 f(i) 为“前 i 个元素的最长递增子序列长度”。但这个定义有问题你无法从前 i-1 个元素的结果直接推导出第 i 个元素加入后的结果因为你不知道前 i-1 个元素的最长递增子序列末尾元素是谁也就无法判断第 i 个元素能不能接在后面。正确的做法是定义f(i) 以 nums[i] 结尾的最长递增子序列长度为什么这样定义因为“以某个元素结尾”把子序列的结束位置固定住了这样后续状态转移时我们只要比较“当前元素能否接在某个前面的元素后面”即可。递归关系初始化 f(i) 1因为单个元素自身可以构成长度为 1 的递增子序列。对于每个 j i如果 nums[j] nums[i]那么 f(i) 可以考虑从 f(j) 1 转移过来。对应的递归思路可以写成f(i) 1 max( f(j) )其中 j i 且 nums[j] nums[i]如果没有任何满足条件的 j那么 f(i) 1。4.2.3 暴力递归到记忆化搜索用 Python 写一个自顶向下的版本。递归函数 dfs(i) 表示“以 nums[i] 结尾的最长递增子序列长度”。def length_of_lis_memo(nums): n len(nums) memo [0] * n def dfs(i): if memo[i] ! 0: return memo[i] best 1 for j in range(i): if nums[j] nums[i]: best max(best, dfs(j) 1) memo[i] best return best ans 0 for i in range(n): ans max(ans, dfs(i)) return ans nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_memo(nums))运行结果4这段代码里 dfs(i) 会递归地去找前面所有比 nums[i] 小的元素把它们的 LIS 长度算出来再加 1。4.2.4 迭代 DP 版本把自顶向下的递归改成自底向上的双重循环def length_of_lis_dp(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) nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_dp(nums))运行结果4这个版本的时间复杂度是 O(n²)空间复杂度是 O(n)。4.2.5 进阶贪心 二分优化到 O(n log n)LIS 还有一个非常经典的优化思路用tails数组维护“长度为 k 的递增子序列的最小末尾元素”。遍历每个元素时在 tails 中二分查找第一个不小于当前元素的位置并替换如果当前元素比 tails 中所有元素都大就追加到末尾。import bisect def length_of_lis_binary(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) nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_binary(nums))结果仍然是4注意tails 数组本身并不一定是真实的 LIS 序列它只是用来辅助计算长度的。这个方法适合只求长度、不要求输出具体序列的场景。4.3 案例三最长公共子序列LCS4.3.1 题目描述给定两个字符串 text1 和 text2返回两个字符串的最长公共子序列的长度。子序列可以不连续但相对顺序必须一致。例如text1 abcde text2 ace 最长公共子序列是 ace长度为 3如果两个字符串没有公共子序列返回 0。4.3.2 递归定义LCS 问题是一个典型的二维 DP。我们定义递归函数f(i, j) text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度其中 i 和 j 可以取 0表示空字符串。递归关系分两种情况如果 text1[i-1] text2[j-1]说明当前两个字符可以匹配那么f(i, j) f(i-1, j-1) 1如果不相等则当前字符不可能同时出现在公共子序列中只能选择丢弃 text1 的最后一个字符或者丢弃 text2 的最后一个字符f(i, j) max( f(i-1, j), f(i, j-1) )递归出口f(0, j) 0 f(i, 0) 0因为空字符串和任何字符串都没有公共字符。4.3.3 暴力递归到记忆化搜索先写一个自顶向下的递归版本def lcs_memo(text1, text2): m, n len(text1), len(text2) memo [[-1] * (n 1) for _ in range(m 1)] def dfs(i, j): if i 0 or j 0: return 0 if memo[i][j] ! -1: return memo[i][j] if text1[i-1] text2[j-1]: memo[i][j] dfs(i-1, j-1) 1 else: memo[i][j] max(dfs(i-1, j), dfs(i, j-1)) return memo[i][j] return dfs(m, n) print(lcs_memo(abcde, ace))运行结果3这里 memo[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。注意递归函数与数组下标从 1 开始和字符串下标差一位。4.3.4 迭代 DP 版本把递归改成双层循环自底向上填表。dp[i][j] 的含义与 memo[i][j] 一致。def lcs_dp(text1, text2): m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i-1] text2[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] print(lcs_dp(abcde, ace))运行结果34.3.5 空间优化LCS 的二维表也可以压缩成一行因为 dp[i][j] 更新时依赖三个位置dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。如果只保留上一行的一维数组我们需要用一个临时变量记录 dp[i-1][j-1]对应左上角的值。def lcs_dp_1d(text1, text2): m, n len(text1), len(text2) dp [0] * (n 1) for i in range(1, m 1): prev 0 # 相当于 dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 保存当前 dp[j]它是下一轮循环的“上一行左上角” if text1[i-1] text2[j-1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j-1]) prev temp return dp[n] print(lcs_dp_1d(abcde, ace))结果还是3这个压缩过程理解起来比一维背包略复杂核心是搞清楚prev变量保存的是哪个历史状态。建议你先跑通二维版本再对照二维表中“当前行覆盖上一行”的过程来理解一维版本不要一上来直接硬啃。5. 动态规划学习中的常见问题与排查思路很多新手自己做 DP 题报错时第一反应是去改代码但其实问题出在“对子问题的定义”上。我整理了刷题时最容易遇到的几类问题帮你对症下药。问题现象常见原因解决思路暴力递归超时存在大量重叠子问题没有加缓存先加 memo 数组改成记忆化搜索递归栈溢出递归深度过大改成自底向上的迭代 DP结果比答案小子问题定义不完整丢失了关键信息检查状态定义是否包含足够信息比如 LIS 需要固定“以当前元素结尾”结果比答案大状态转移时错误地重复使用了某个元素检查是否需要对容量、下标、选择次数做限制比如 0-1 背包需要逆序更新一维数组一维空间优化后结果错误更新方向错误导致状态被覆盖回退到二维版本逐个打印 dp 表排查边界条件为空数组/空串时出错没有处理 base case先把 n0、m0 等极端输入跑一遍5.1 如何定位递归中的重复计算如果你不确定自己的递归是否存在大量重复计算可以在递归函数里加一个计数器或者打印递归调用参数。比如def dfs(i, c): print(fcall dfs({i}, {c})) ...如果看到相同的 (i, c) 反复出现就说明存在重叠子问题有必要使用记忆化搜索。5.2 状态定义不清晰导致的玄学报错这是 DP 新手最隐蔽的坑。以 LIS 为例如果你把 f(i) 定义成“前 i 个元素的最长递增子序列长度”那么当 nums[i] 很小但前面的最长递增子序列末尾很大时你是无法判断能不能把 nums[i] 接上去的。这会导致递推关系无法建立或者结果错误。遇到这种情况解决问题的关键不是改代码而是回头重新定义状态。一个常用的技巧是增加约束条件让子问题之间能够“衔接”。LIS 中“以第 i 个元素结尾”就是一种常见的约束。5.3 对着题解能看懂自己写就卡住这是正常的学习曲线。建议你不要只看题解代码而是找一道中等难度 DP 题按照“递归定义 → 暴力递归 → 记忆化 → 迭代 DP”的顺序自己从头到尾完整推一遍。这个过程会强迫你把“状态怎么转移”讲清楚而不是被动接受现成的 dp 方程。6. 动态规划的最佳实践与刷题建议6.1 先画递归树再写代码拿到一道 DP 题不要急着敲键盘。在草稿纸上画出小规模输入的递归树标注哪些节点被重复计算。这个动作能帮你同时验证“子问题是否重叠”和“递归关系是否正确”。比如爬楼梯问题n5 的递归树中 f(3) 会出现两次f(2) 会出现三次画出来之后你自然理解为什么要记忆化。6.2 状态定义口诀最后一步看什么状态就存什么如果你不知道 dp 数组的每个维度代表什么可以问自己一个终极问题当我只差最后一步就能得到答案时我需要知道哪些信息背包问题需要知道还剩多少容量以及已经处理到第几件物品所以状态是 f(i, c)。LIS需要知道当前递增子序列以哪个元素结尾所以状态是 f(i)。编辑距离需要知道两个字符串分别处理到哪个位置所以状态是 f(i, j)。这个“最后一步分析法”有时候比生搬套路更有效建议你在做题时反复练习。6.3 用一维还是二维取决于状态依赖关系很多同学会陷入“必须写出空间最优解”的执念。实战中建议你先用最直观的二维 DP 写出正确版本提交通过后再考虑能否用滚动数组或一维数组优化优化前用注释列出一维数组更新时可能覆盖的旧值再动手改代码。空间优化是锦上添花不是雪中送炭。面试时如果时间紧张先写出正确解比写出最优解更重要。6.4 刷题顺序建议如果你的动态规划还处于入门阶段不推荐直接挑战困难题。可以参考下面这个难度递增路径爬楼梯、斐波那契数列体会“递推 空间压缩”不同路径、最小路径和体验二维 DP 表格怎么填最长递增子序列、最长公共子序列练习子序列类模型0-1 背包、完全背包掌握最经典的背包模型打家劫舍系列、买卖股票系列练习状态机式 DP区间 DP、树形 DP进阶方向按需学习。每一步都要保证自己能用“递归 → 记忆化 → 递推”的流程独立推导出来再进入下一类题。6.5 关于代码的工程习惯刷题代码和生产代码要求不同但以下习惯值得保持函数命名清晰让别人一眼知道这个函数在算什么状态数组的语义用注释说明例如dp[c]表示“容量为 c 时的最大价值”把 base case 单独写清楚不要藏在循环条件里写完代码后用一组边界数据自测空输入、最小输入、最大输入、相等元素输入。如果你在本地 IDE 中练习还可以自己写一个简单的测试函数批量断言结果便于后续回归def test_lis(): assert length_of_lis_dp([10, 9, 2, 5, 3, 7, 101, 18]) 4 assert length_of_lis_dp([0]) 1 assert length_of_lis_dp([]) 0 print(all test cases passed) test_lis()7. 总结动态规划并不可怕可怕的是用背题的方式去学它。这篇文章的核心观点是状态转移方程不是背出来的而是从递归定义里一步步推出来的。我们完整走通了三条推导路径0-1 背包从 f(i, c) 的递归定义出发经过记忆化搜索改写成二维递推最终压缩成一维逆序更新最长递增子序列从 f(i) 表示“以 nums[i] 结尾”的递归定义出发推导出 O(n²) 的 DP再介绍了 O(n log n) 的二分优化最长公共子序列从二维递归 f(i, j) 出发对照字符相等和不相等两种情况推导出二维填表逻辑再分析了空间压缩的细节。如果你能把这三种模型的推导过程自己复现一遍再去做 LeetCode 上的同类变体题比如跳跃游戏、编辑距离、零钱兑换会发现这些题远没有想象中难。关键在于先想清楚一件事我正在求解的子问题是什么它和我已经解决过的更小子问题之间是什么关系想清楚这个代码只是顺手的事。拿一道题练手吧LeetCode 300 最长递增子序列或者 LeetCode 1143 最长公共子序列先别看题解按文中的三步法自己推一遍。遇到卡壳的地方回来对照文章的推导过程看看自己是在状态定义、递归关系、还是边界处理上出了问题。多推几道你就能慢慢建立属于自己的动态规划直觉了。