动态规划不靠背：从递归到记忆化搜索再到递推DP的完整推导指南

做 LeetCode 刷题很多同学都有一个共同体验动态规划看题解时全懂关上答案自己写还是不知道 dp 数组怎么开、转移怎么写。更常见的做法是去背状态转移方程结果 LeetCode 上一换题就废。这篇笔记想换一个顺序来写 DP不背公式而是从你本来就会的递归出发一步步把递归改成记忆化搜索再改成递推 DP。只要走完这三步背包、LIS、LCS 这些经典题就不再是“玄学”而是一套可以重复使用的思考方法。先给一个明确判断动态规划不是靠背转移方程学会的它是把暴力递归中的重复计算缓存起来再把递归改成填表。所以真正的入口不是 DP 公式而是递归。读完这篇文章你会拿走三样东西一套“暴力递归 → 记忆化 → 递推 DP”的通用推导流程背包、LIS、LCS 三类高频题的最小可运行代码以及自己遇到新题时判断“该不该用 DP、状态怎么定义”的思考清单。1. 动态规划到底在解决什么问题很多教程一上来就甩定义动态规划是“把原问题拆成若干子问题保存子问题结果避免重复计算”。这个解释没有错但大多数小白听完仍然不会做题因为它缺少最关键的一步你怎么知道哪些问题能拆拆完之后状态怎么表示动态规划本质上是递归的优化。先用一个最简单的视角理解原问题可以拆成若干规模更小的子问题。子问题和原问题结构相同只是输入更小。不同的拆分路径会大量碰到同一个子问题造成重复计算。第一点对应“最优子结构”第三点对应“重叠子问题”。这两个词不需要背你只要在写递归时看到了重复计算就说明这道题有机会用 DP 优化。另一个容易让新人迷惑的概念是“无后效性”。通俗地解释当我们已经算出第 i 个子问题的答案后后面更大的状态只需要直接使用这个结果不需要关心这个结果是怎么选出来的。比如你算出到达第 10 级台阶的方法数是 dp[10]之后算 dp[11] 时只需要 dp[10] 这个数字不用再问“你是先迈了一步还是迈了两步才到第 10 级”。如果状态被定义成这样就能写成 DP如果当前结果还依赖此前完整选择路径那说明状态设计有问题。有了这个基础我们再统一术语。动态规划里经常出现三个词状态dp[i] 或 dp[i][j] 表示什么含义。转移当前状态由哪些更小的状态推导出来。初始化边界子问题的答案也就是 dp 的起点。动态规划还有两种实现方向后面会反复用到方向别名思路特点自顶向下递归 备忘录从大问题往下递归用一个 memo 记录已经算过的子问题代码直观接近暴力递归自底向上递推/填表 DP从最小边界开始按顺序填充 dp 数组通常更快也是题解最常见的写法这篇文章的核心观点很简单自顶向下和自底向上的代码虽然长得不同但它们推导同一个状态转移方程。你只要熟练地从暴力递归开始自然能写出记忆化搜索再把它翻译成递推 DP。下面用一个最经典的题走通这个流程。2. 从递归到递推的最小闭环先做爬楼梯LeetCode 70 题“爬楼梯”是练习这个流程成本最低的题目因为它的状态转移方程只有一个维度没有数组选择和字符串比较的干扰。题目描述很直接你正在爬楼梯每次可以爬 1 级或 2 级台阶问爬到第 n 级台阶有多少种不同方法。2.1 先写暴力递归遇到这种题先别想 dp 数组只想一个问题到达第 n 级台阶前你最后一步做了什么只可能是两种情况从第 n-1 级跨 1 级上来。从第 n-2 级跨 2 级上来。所以到达第 n 级的方法总数 到达第 n-1 级的方法数 到达第 n-2 级的方法数。这是典型的递归思想把大问题缩小成两个更小的子问题。接下来写出暴力递归#include iostream using namespace std; // 到达第 n 级台阶的方法数 int climbStairsRecursive(int n) { if (n 1) return 1; // 第 0 级和第 1 级都只有 1 种理解方式 return climbStairsRecursive(n - 1) climbStairsRecursive(n - 2); } int main() { int n 10; cout climbStairsRecursive(n) endl; return 0; }这段代码在 n 较小时能算出答案但 n45 时已经非常慢了。原因是它把大量重复的子问题反复计算了一遍算 f(10) 需要算 f(9) 和 f(8)算 f(9) 又需要算 f(8) 和 f(7)。这里的 f(8) 在递归树里出现了很多次每次出现都会重新执行整棵子树这就是“重叠子问题”。2.2 加一个 memo变成记忆化递归先画出递归树你会发现大量相同节点。既然同一个 f(k) 算一次就够了我们用一个数组存结果下次再需要时直接返回这就是记忆化搜索也叫自顶向下 DP。#include iostream #include vector using namespace std; int dfs(int n, vectorint memo) { if (n 1) return 1; if (memo[n] ! -1) return memo[n]; // 已经算过直接返回 memo[n] dfs(n - 1, memo) dfs(n - 2, memo); return memo[n]; } int climbStairs(int n) { vectorint memo(n 1, -1); return dfs(n, memo); } int main() { int n 10; cout climbStairs(n) endl; return 0; }到这里代码已经足够通过 LeetCode。相比暴力递归它只是把中间结果存下来时间复杂度从指数级降到了 O(n)。2.3 改成自底向上的递推 DP观察递归代码可以发现递归从 n 一路向下问到边界再逐层返回。既然栈会把结果返回给上层我们不如直接从边界开始向上填表避免递归本身的额外开销。先定义 dp[i] 表示爬到第 i 级台阶的方法数初始化 dp[0] 1dp[1] 1然后从 i2 循环到 n#include iostream #include vector using namespace std; int climbStairs(int n) { if (n 1) return 1; vectorint dp(n 1, 0); dp[0] 1; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } int main() { int n 10; cout climbStairs(n) endl; // 输出 89 return 0; }运行这段代码当 n10 时输出 89n1 时输出 1。至此你已经完成了一次完整的推导闭环暴力递归 → 记忆化递归 → 递推 DP。后面所有动态规划题思考顺序都应该是这样的。背下来的状态转移方程只是最终结果而你真正需要学会的是“为什么状态能这样转移”的推导过程。3. 01背包问题其实就是“选还是不选”的递归爬楼梯足够简单但它只包含一维状态。真正让很多小白在 DP 上第一次受挫的往往是 01背包问题。我们先不看“背包”这个名词包装直接看它的递归本质。问题描述有 n 件物品每件物品有重量 weight[i] 和价值 value[i]背包容量是 capacity问怎么选物品能让装入背包的总价值最大且每件物品最多选一次。这是一个典型的最优化问题。用递归去想时你只需要站在某一件物品面前做一个决定拿还是不拿。3.1 从选择的角度写暴力递归假设我们用一个函数 dfs(i, rest) 表示从第 i 件物品开始往后考虑背包还剩 rest 容量时能获得的最大价值。那么对第 i 件物品只有两种可能不拿它结果等于 dfs(i 1, rest)。拿它前提是 rest weight[i]结果等于 dfs(i 1, rest - weight[i]) value[i]。最后取这两种选择的最大值。这个思路完全不需要背任何背包公式它就是一个“选与不选”的枚举。#include iostream #include vector #include algorithm using namespace std; // 从 index 开始考虑背包剩余容量为 rest int dfs(int index, int rest, const vectorint weight, const vectorint value) { if (index (int)weight.size()) return 0; // 没有物品可选 int res dfs(index 1, rest, weight, value); // 不选当前物品 if (rest weight[index]) { // 能选才选 res max(res, dfs(index 1, rest - weight[index], weight, value) value[index]); } return res; } int main() { vectorint weight {2, 1, 3, 2}; vectorint value {3, 2, 4, 2}; int capacity 5; cout dfs(0, capacity, weight, value) endl; // 输出 7 return 0; }示例数据中最优选择是物品 2重量 1 价值 2、物品 3重量 3 价值 4、物品 4重量 2 价值 2总重量 6这里容量是 5选物品234 总重量是 1326超过容量 5所以不是这个选择。正确最优选是物品 0重量2 价值3、物品1重量1 价值2、物品3重量2 价值2总重量5总价值7。上面代码会输出 7。3.2 看到重复子问题加 memo 改成记忆化在递归过程中可能出现“不同选择路径最后都进入同一个 (index, rest) 状态”的情况。例如先不选第一件再选第二件和先选第二件再遇到剩余容量相同后续的决策空间完全相同。为了不重复计算用二维 memo 记录答案#include iostream #include vector #include algorithm using namespace std; int dfs(int index, int rest, const vectorint weight, const vectorint value, vectorvectorint memo) { if (index (int)weight.size()) return 0; if (memo[index][rest] ! -1) return memo[index][rest]; int res dfs(index 1, rest, weight, value, memo); if (rest weight[index]) { res max(res, dfs(index 1, rest - weight[index], weight, value, memo) value[index]); } memo[index][rest] res; return res; } int main() { vectorint weight {2, 1, 3, 2}; vectorint value {3, 2, 4, 2}; int capacity 5; vectorvectorint memo(weight.size() 1, vectorint(capacity 1, -1)); cout dfs(0, capacity, weight, value, memo) endl; // 7 return 0; }3.3 自底向上填二维表当你能写出记忆化递归递推 DP 就只是把递归倒过来。观察递归函数可变参数只有 index 和 rest所以 dp 数组也应该是二维的。定义 dp[i][c] 表示考虑前 i 件物品背包容量为 c 时能获得的最大价值。则转移公式为不选第 i 件dp[i][c] dp[i-1][c]。选第 i 件如果 c weight[i-1]dp[i][c] max(dp[i][c], dp[i-1][c-weight[i-1]] value[i-1])。注意代码中用到 weight[i-1]因为数组下标从 0 开始但 dp 的第 i 行代表前 i 件物品。这是新手最容易下标错位的地方。#include iostream #include vector #include algorithm using namespace std; int knapsack01(const vectorint weight, const vectorint value, int capacity) { int n weight.size(); vectorvectorint dp(n 1, vectorint(capacity 1, 0)); for (int i 1; i n; i) { int w weight[i - 1]; int v value[i - 1]; for (int c 0; c capacity; c) { dp[i][c] dp[i - 1][c]; // 第 i 件物品不放入背包 if (c w) { dp[i][c] max(dp[i][c], dp[i - 1][c - w] v); } } } return dp[n][capacity]; } int main() { vectorint weight {2, 1, 3, 2}; vectorint value {3, 2, 4, 2}; int capacity 5; cout knapsack01(weight, value, capacity) endl; // 输出 7 return 0; }运行这段程序会输出 7对应选择物品 1重量 2 价值 3、物品 2重量 1 价值 2、物品 4重量 2 价值 2总重量 5总价值 7。3.4 一维滚动数组为什么要倒序更新很多题解会把 01背包 压缩成一维数组vectorint dp(capacity 1, 0); for (int i 0; i n; i) { for (int c capacity; c weight[i]; --c) { dp[c] max(dp[c], dp[c - weight[i]] value[i]); } }这里真正容易踩坑的地方是容量必须倒序循环。原因是 dp[c-weight[i]] 如果在本轮物品中被先更新了就会导致同一件物品被重复选择这不符合 01背包“每件最多选一次”的约束。倒序更新可以保证 dp[c-weight[i]] 仍然是上一轮循环的结果。一维数组并不是初级学习者必须马上掌握的但它能帮助你理解背包问题的本质只有“选”和“不选”两种状态而倒序更新是在防止同一个物品被重复拿。4. 最长递增子序列 LIS为什么 dp[i] 要定义成“以 i 结尾”LeetCode 300 题求最长递增子序列 lengthOfLIS它的难点是状态下定义很容易走偏。先区分一个概念子数组是连续的子序列可以不连续。例如 [10,9,2,5,3,7,101,18]最长递增子序列是 [2,3,7,101] 或 [2,5,7,101]长度是 4。4.1 从递归视角定义状态假设我们想求“以第 i 个元素结尾的最长递增子序列长度”记为 f(i)。那么序列的倒数第二个元素应该在前面的某个位置 j并且满足j inums[j] nums[i]如果找到了这样的 j那么以 nums[i] 结尾的递增子序列长度至少是以 nums[j] 结尾的最长递增子序列长度再加 1。如果前面没有任何元素小于 nums[i]那么以 nums[i] 结尾的递增子序列长度就是 1。这个递归描述可以轻易写成递推dp[i] 1 for j in [0, i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1)为什么 dp[i] 要定义成“以 nums[i] 结尾”因为递增子序列需要一个明确的“当前最后一个值”才能判断后续能不能继续接。如果只定义成“前 i 个元素里的最长递增子序列长度”你无法知道最后一个数是多少也就无法继续比较大小这就是最常见的最初状态设计错误。你要的答案是所有 dp[i] 中的最大值而不是 dp[n-1]。4.2 LIS 的完整可运行代码#include iostream #include vector #include algorithm using namespace std; int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; } int main() { vectorint nums {10, 9, 2, 5, 3, 7, 101, 18}; cout lengthOfLIS(nums) endl; // 输出 4 return 0; }4.3 进阶提醒还有 O(n log n) 的解法LIS 还有一个常见优化用贪心加二分维护“递增子序列的最小末尾元素”。它的做法是遍历数组时如果当前数比维护数组末尾大就追加否则用 lower_bound 找到第一个不小于当前数的位置并替换掉。这个方法常常在面经中出现但对于刚学 DP 的小白建议先把 O(n^2) 的朴素递推吃透。你只要理解“dp[i] 以 i 结尾是为了支持后续比较”就已经解决了这道题最重要的思维难点二分优化是后面水到渠成的事情。5. 最长公共子序列 LCS二维 DP 的经典入门LeetCode 1143 题求两个字符串的最长公共子序列长度。例如 text1 abcdetext2 ace最长公共子序列是 ace长度是 3。注意这里的子序列也不需要连续只需要保持相对顺序一致。5.1 二维状态的递归推导两个字符串互相比较只用一个下标很难表示进度于是自然会想到用两个下标。定义 dp[i][j] 表示text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。比较两个串的末尾字符时有两种情况如果 text1[i-1] text2[j-1]这两个字符相等它俩可以作为公共子序列的最后一个字符。长度至少是 dp[i-1][j-1] 1。反证法理解如果最优公共子序列不用这一对相等的末尾字符那把它接到公共子序列末尾也不会破坏顺序只会更长所以最优解一定可以包含它。如果 text1[i-1] ! text2[j-1]末尾字符不相等那么当前公共子序列不可能同时以这两个字符结尾。它要么等于 text1 去掉末尾字符后的结果 dp[i-1][j]要么等于 text2 去掉末尾字符后的结果 dp[i][j-1]取两者最大值。这个递推式不需要背它是你比较“两个串当前末尾”时自然产生的逻辑分支。5.2 LCS 的完整代码#include iostream #include string #include vector #include algorithm using namespace std; int longestCommonSubsequence(string text1, string text2) { int n text1.size(); int m text2.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { 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[n][m]; } int main() { string a abcde; string b ace; cout longestCommonSubsequence(a, b) endl; // 输出 3 return 0; }当输入为 abcde 和 ace 时运行结果输出 3。如果你在本地调试时把 i、j 从 1 开始循环并且比较时使用 text1[i-1] 和 text2[j-1]就不会出现越界问题。常见的错误是把字符比较写成 text1[i] 和 text2[j]导致访问越界或漏掉首字符。5.3 LCS 的延伸价值LCS 不止是一道题它是很多字符串 DP 的基础。例如编辑距离题目中Word A 变成 Word B 的最少操作数会用到和 LCS 类似的二维状态转移。如果你能把 LCS 的推导流程想清楚后面学编辑距离会轻松很多。6. 遇到新题怎么判断它是不是动态规划讲了几个经典模型之后你很自然会问考试或面试时拿到一道从没见过的题怎么知道该用 DP我的判断标准是三个信号题目问的是“最大/最小/最长/最短/方案数”而不是要求输出具体选择路径。原问题可以拆成若干相同结构的子问题且子问题之间重叠。决策只影响当前状态和未来可选择的范围但不影响已经被计算过的信息。第一条最直观求最长递增子序列、最长公共子序列、最小编辑距离、达到目标金额的最少硬币数这类极值问题天然适合 DP。如果题目要求输出具体路径通常需要额外记录选择前驱但第一步判断仍然是 DP。第二条可以用来做递归测试。你先尝试写一个暴力递归函数看函数的参数里有没有反复出现的相同状态。如果有就能用记忆化或递推优化。比如 01背包 的 dfs 参数是 index 和 rest爬楼梯的递归参数就只是 nLCS 的递归参数是 i 和 j。递归函数中会变化的参数基本就是之后 dp 数组的维度。第三条要重复一遍“无后效性”的含义当你写出 dp[i] 时它只作为数值参与后续转移不需要知道内部是怎么选出来的。如果你发现自己需要“知道第 i 次选择之后还剩多少容量”或“当前子序列最后一个元素的值”就把这些信息放进状态里。LIS 的“以 i 结尾”、背包的“剩余容量 rest”都是在补充这种必要信息。一个实用的操作步骤是步骤要问的问题示例1. 定义状态dp[i] 或 dp[i][j] 表示什么爬楼梯到第 i 级的方法数2. 寻找子问题当前结果由哪些更小状态得到背包不选/选第 i 件3. 确定转移用代码写出来不先背公式LCS末字符相等/不等4. 初始化边界空串、容量 0、长度为 1 的情况dp[0][j]0dp[i][0]05. 确定遍历顺序小状态先算大状态后算一般从左到右、从上到下做判断题时最忌讳的是“感觉像 DP 就硬套背包模板”。更好的策略是先把暴力递归写在草稿纸上哪怕复杂度很差也能帮你理解状态。状态想清楚了DP 就是递归的缓存加顺序遍历。7. 动态规划常见错误与排查思路很多小白刷 DP 题时是在“背答案”所以遇到 WA 或 TLE 很难自己定位问题。下面是几个高频错误建议保存成自己的排查清单问题现象可能原因排查方式解决思路答案比预期大背包一维数组用正序遍历导致同一件物品被重复选检查滚动数组循环方向01背包 容量倒序遍历完全背包可以正序先确认题目类别下标越界dp 下标与数组下标混用例如比较 text1[i] 而不是 text1[i-1]打印 dp 表或加边界输出牢记 dp[i] 含义注意字符数组下标偏移答案一直不变或为 0初始化值设置不对比如求最小值时初始化为 0检查 dp 初始值求最小值通常初始化为很大的数求最大值通常初始化为很小的数递归超时忘了加记忆化直接提交暴力递归看是否 submiss 超时递归函数里加 memo或改写成递推最终答案取错位置误以为答案一定在 dp[n-1]检查题目要求的是“以末尾结尾”还是全局最优LIS 需要在循环中维护 ans不一定返回 dp 最后一个值状态定义不清晰转移写不出来可变信息没有全部放进 dp回到递归列出所有可变参数把递归函数参数变成 dp 维度这里特别提醒LIS 的答案不是 dp[n-1]因为最长递增子序列不一定以数组最后一个元素结尾需要在填表过程中不断取 max。类似的陷阱在“最大子数组和”里也出现过这类泛化最优问题要单独维护全局答案。8. 下一步练习路线按模型而不是按题号堆积掌握了“递归 → 记忆化 → 递推”这一套接下来要做的不是一口气刷几十道题而是把经典模型练到能凭直觉推导出来。下面是按模型划分的练习顺序从今天讲的三类题开始第一梯队1-2 天爬楼梯、斐波那契数、使用最小花费爬楼梯。这些题适合反复练“暴力递归 → 记忆化 → 递推”的三步转换形成肌肉记忆。第二梯队3-5 天01背包 与它的变体。先做 416. 分割等和子集因为它本质上是“从数组中选一些数能否凑出总和的一半”是一个 01背包 的判定版本。再做 322. 零钱兑换注意这题是“每一种硬币可以用无限次”属于完全背包和一维 01背包 的遍历顺序正好相反。做这两道题时重点观察“物品能用几次”如何影响循环方向。第三梯队1-2 天LIS 和 LCS。除了 LeetCode 300 和 1143可以再做 674. 最长连续递增序列这题能帮你区分“连续”和“不连续”的状态转移差异。之后再挑战 72. 编辑距离你会看到二维 DP 的威力。第四梯队选做多维背包、分组背包等。当 01背包 和完全背包都比较熟练后可以去看一下“分组背包至少选一个”“多维背包”这类进阶模型。它们不是全新的算法而是给了 dp 数组更多维度把背包问题的“选择模型”推广到真实约束中。从输入材料里的高频词看这类变体在竞赛题和 LeetCode 周赛里都很常见但你没必要一开始就啃。建议每天只做一道 DP 题做完后不看答案在纸上用今天的方法重新推一遍。如果你能做到“不选dp[i-1][c]选dp[i-1][c-w]v”不是背出来的而是从递归函数现场翻译出来的那 DP 就算入门了。9. 最后想强调的别把 DP 学成记忆题库这篇文章真正想解决的问题不是“让你会做三道题”而是纠正一个学习顺序不要一上来就背状态转移方程。背包、LIS、LCS 这三个词往往被包装成“模板题”但模板只能帮你应对原题真正帮你应对变体的是你从递归推到 DP 的能力。以后刷题时建议给自己定一条规则遇到动态规划题先写一个返回答案的递归函数哪怕它很慢。只要你写出了 dfs 的参数状态定义就自然出来了只要发现参数相同的调用会被重复计算记忆化方案就出来了只要把递归的执行顺序倒过来从边界开始填表递推 DP 就出来了。这三步走完代码的每一行都有了来源。动态规划不是靠灵感的算法它是一套有章可循的建模方法。下个阶段可以往区间 DP、树形 DP、状态压缩 DP 扩展但所有延伸题型都建立在同一个基本功上理解递归拆解、理解状态含义、理解重复子问题。把这几道经典题按“递归到 DP”的顺序再过一遍比囫囵吞枣刷五十道题更值得。建议把本文收藏起来当刷题卡住时回到这个推导流程它会比记忆中的某个方程更可靠。