2026/9/4 11:31:15
FEATURED · 精选文章 
动态规划恐怕是 LeetCode 上劝退率最高的一块。很多人一刷到“动态规划”四个字第一反应不是打开编辑器而是先去找题解里的状态转移方程抄下来套循环跑通然后松了一口气。可下次遇到一道同类型的新题状态定义稍微换一下又不会了。问题不在题目难度而在你从一开始就在背一个没有推导过程的公式。这篇文章想换一个训练思路不背状态转移方程而是从递归一步步把 DP 推出来。你会发现状态转移方程不是从天而降的公式而是你写的递归函数本身的“运行规律”。只要你会写递归能看出重复计算在哪里动态规划其实是被动得到的优化结果。文章会以爬楼梯、01 背包、LIS最长递增子序列、LCS最长公共子序列四个经典场景为例把同一套推导链路完整走一遍。适合这类读者DP 题只会套模板换个包装就不会已经刷过一部分 LeetCode 简单题但碰到中等的动态规划题就卡住或者你只是想搞清楚“递归、记忆化搜索、递推 DP 到底是什么关系”。这篇文章不是题解合集也不会让你背任何公式但读完以后你可以自己把状态转移方程写出来。1. 状态转移方程不是背出来的先想清楚这个问题先回答一个基础问题为什么状态转移方程难背因为绝大多数教材和题解默认你已经接受了“状态”这个概念。比如常用的写法dp[i]、dp[i][j]看起来短小精悍但它背后藏着三个问题i到底表示什么dp[i]的答案是怎么从更小的dp值堆出来的边界条件为什么是那样写如果你跳过递归推导直接盯着这行公式看等于把“因”和“果”一起摆在面前但中间的逻辑链条完全缺失。你今天能看懂明天换个条件照样不会。动态规划真正依赖的只有两个前提。第一个是最优子结构意思是原问题的最优解可以由子问题的最优解组合出来。比如爬楼梯到第n阶的总方法数等于到第n-1阶的方法数加第n-2阶的方法数因为最后一步要么跨一阶要么跨两阶。第二个是重叠子问题意思是求解过程中同一个子问题会被反复算很多次。爬楼梯的暴力递归会反复求dfs(3)、dfs(2)这就是重叠。理解了这两个前提之后动态规划的完整推导链就非常清楚了先写出能表达“原问题怎么拆成子问题”的递归函数再看递归树中是否有大量重复节点有重复再加缓存最后把带缓存的递归改写成从底层开始向上填表的循环。这个过程不需要灵感也不需要背诵只需要按顺序执行。你甚至可以把 DP 理解成递归的“缓存优化版本”只是这个缓存不再用字典而是写进了数组里。2. 从递归到 DP以爬楼梯为例子2.1 题目背景LeetCode 第 70 题爬楼梯是动态规划入门的首选。题目要求很直接每次可以爬 1 阶或 2 阶问爬到第n阶有多少种不同的方法。这个题如果直接用数学排列组合去算会很别扭但用递归来想就非常简单到第n阶的走法等于到第n-1阶的走法加上到第n-2阶的走法因为你最后一步只有这两种可能。2.2 先写一个最朴素的暴力递归不要一上来就写dp数组先写递归函数。递归函数天然能表达“从当前问题拆到子问题”的结构。下面是最直接的版本def climbStairs(n): if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这个代码能通过人脑模拟但在 LeetCode 上大概率超时。原因来自递归树求climbStairs(5)时要先求climbStairs(4)和climbStairs(3)求climbStairs(4)又要再求一次climbStairs(3)。也就是说climbStairs(3)被重复算了。当n越来越大重复节点的数量是指数级增长的。这就是动态规划里最核心的“重叠子问题”。2.3 加一个缓存记忆化搜索重复算很浪费那就直接把算过的结果存下来。Python 里可以用lru_cache非常轻松地完成这件事from functools import lru_cache def climbStairs(n): lru_cache(None) def dfs(i): if i 2: return i return dfs(i - 1) dfs(i - 2) return dfs(n)这里dfs(i)的定义是“爬到第i阶有多少种方法”。递归函数内部依然调用dfs(i - 1)和dfs(i - 2)但因为有缓存同样的i只会真正计算一次。时间复杂度从指数级降到了O(n)。这种写法有个名字叫“自顶向下动态规划”也叫记忆化搜索。对于入门者我建议你至少在前期强制自己先写这种递归版本。因为它和问题描述最接近不容易把状态定义搞反。很多人在二维 DP 里分不清dp[i][j]的i和j哪个是行、哪个是列就是因为直接从填表开始完全没有经历“递归函数参数即状态”这一步。其实递归函数dfs(i)里的参数i就是 DP 状态里的维度递归函数里选择的拆分方式就是状态转移方向的来源。2.4 把递归改写成递推 DP现在再来看递推版本你会发现一切都有迹可循。既然dfs(i) dfs(i - 1) dfs(i - 2)并且我们知道i 1时答案是 1i 2时答案是 2那么就可以从 1 往上填表def climbStairs(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]这里的dp[i]其实就是刚才递归函数里的dfs(i)dp[i] dp[i - 1] dp[i - 2]就是递归函数去掉返回逻辑后剩下的赋值语句。你不需要单独背状态转移方程因为你已经把递归函数原封不动地翻译成了循环。唯一的区别是递归是等结果需要时才向上层返回而递推是从最小问题开始按顺序把所有状态都算一遍。这个例子可以继续压缩空间因为每次只依赖前两个状态用两个变量滚动就可以。但那是优化阶段的动作不是推导阶段的动作。对于新手我建议前几道题老老实实写完整数组把表打出来看清楚每个格子是怎么被算出来的再谈优化。3. 动态规划通用推导五步法爬楼梯跑通之后可以把经验升华为一套通用步骤。以后做任何动态规划题都可以按下面五步走。第一步定义状态。问自己一个问题如果我写递归函数参数应该是什么这组参数就是状态的维度。比如爬楼梯是dfs(i)表示第i阶的答案背包通常是dfs(i, c)表示处理到第i个物品、剩余容量为c时的答案LIS 是dfs(i)表示以第i个位置元素结尾的答案。状态定义是整个动态规划里最不能省的一步它决定了后面所有代码的写法。第二步写暴力递归主体。把当前问题看成从某个选择集合里挑一个子问题。例如爬楼梯的最后一步可以选择跨一阶或两阶背包的当前物品可以选择拿或不拿LCS 的当前字符可以匹配或不匹配。这一步要写一个没有缓存的递归先不要担心性能只求逻辑正确。第三步找边界条件和返回值。边界条件就是递归的出口。爬楼梯是n 2直接返回背包是物品数量为负或容量为 0 时返回 0LIS 是只有一个元素时返回 1。边界别硬记要回到状态定义里推导想清楚“当参数最小的时候答案显然是多少”。第四步检查是否存在重叠子问题。在草稿纸上画出递归树观察同一个(i)或(i, c)是否被多个分支调用。如果没有重叠说明这个问题用普通分治或回溯就能解决如果有重叠才需要缓存也就是进入真正的动态规划。第五步把递归改写成递推。把递归函数里的“返回某个值”改成“把某个格子的值算出来”。递推方向一般和递归参数减小的方向相反。递归从大问题拆到小问题递推则从小问题开始累积到大问题。改写要同时确定两层循环的顺序这往往是背包类问题最容易出错的地方。其实这套流程就是很多教材里说的“状态定义 状态转移 边界条件 遍历顺序”但它的出现顺序是自然推导出来的不需要死记。为了让你看到这套方法的泛化能力下面三个经典模型都会按同样的路径走一遍。4. 背包问题从 01 背包开始背包问题在 LeetCode 里非常重要尤其是 01 背包和完全背包会演变成“分割等和子集”“目标和”“零钱兑换”等热门题。这里先用 01 背包讲透遍历顺序。题目模型是有n个物品第i个物品的重量是weights[i]价值是values[i]每个物品只能选一次背包总容量是capacity求能装下的最大总价值。第一步定义状态。我们需要同时知道“处理到哪个物品”和“当前剩余容量”所以递归函数有两个参数dfs(i, c)表示“从第 0 到第 i 个物品中做选择剩余容量为 c 时能获得的最大价值”。第二步写递归主体。对当前第i个物品只有两种选择不拿那么结果等于dfs(i - 1, c)拿那么需要先判断weights[i] c然后结果是dfs(i - 1, c - weights[i]) values[i]。取两者最大值即可。from functools import lru_cache def knapsack01(weights, values, capacity): n len(weights) lru_cache(None) def dfs(i, c): if i 0: return 0 if weights[i] c: return dfs(i - 1, c) return max(dfs(i - 1, c), dfs(i - 1, c - weights[i]) values[i]) return dfs(n - 1, capacity) print(knapsack01([1, 3, 4], [15, 20, 30], 4)) # 输出 35这里用i 0作为递归出口表示没有物品可选时价值为 0。dfs(i - 1, c - weights[i])里的i - 1保证了每个物品最多被选一次因为一旦拿走当前物品后面的递归只会继续往前面的物品选择不会再回头拿自己。这个细节是 01 背包和完全背包的本质区别。第三步改写成二维递推 DP。把递归参数映射成数组下标dp[i][c]表示“前 i 个物品容量为 c”时的最大价值。这里让i从 1 到n对应物品下标i-1从而让dp[0][c] 0作为没有物品时的边界。def knapsack01(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for c in range(capacity 1): if weights[i - 1] c: dp[i][c] dp[i - 1][c] else: dp[i][c] max( dp[i - 1][c], dp[i - 1][c - weights[i - 1]] values[i - 1] ) return dp[n][capacity] print(knapsack01([1, 3, 4], [15, 20, 30], 4)) # 输出 35二维版本虽然空间大一点但逻辑和递归完全一致适合用来验证理解。当你发现dp[i]这一行只依赖dp[i-1]那一行时就可以尝试用一维数组滚动更新def knapsack01(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): # 必须倒序遍历容量防止同一个物品被选多次 for c in range(capacity, weights[i] - 1, -1): dp[c] max(dp[c], dp[c - weights[i]] values[i]) return dp[capacity] print(knapsack01([1, 3, 4], [15, 20, 30], 4)) # 输出 35这段代码里最容易踩的坑就是内层容量循环的顺序。为什么必须倒序因为一维数组里没有“行号”可以区分当前物品是否已经被更新。如果正序遍历容量那么计算大容量dp[c]时会用到刚刚被当前物品更新过的dp[c - weights[i]]这相当于同一个物品已经在前面容量较小的状态里被放入过一次再放一次就变成一个物品可以无限使用的完全背包了。倒序遍历保证每个容量只使用上一轮旧数据符合 01 背包“每件物品只能选一次”的约束。建议你亲手跑一遍这个例子把每次更新后的dp数组打印出来。你会发现倒序时第i个物品产生的影响只向右推进一次改成顺序时一个物品的价值会在同一轮里不断叠加。看明白了这一点背包变种题就再也不会被遍历顺序卡住。5. 最长递增子序列 LIS子序列问题的入门模型LIS 是 LeetCode 上另一类经典动态规划题代表问题是“最长递增子序列”。注意子序列不要求连续但元素之间的相对顺序必须保持。比如nums [10, 9, 2, 5, 3, 7, 101, 18]的最长递增子序列长度是 4一个答案是[2, 3, 7, 101]。这道题很多人的第一反应是“枚举所有起点”但很快会发现很难判断后续元素是否递增。更自然的状态定义是dfs(i)表示以nums[i]这个元素结尾的最长递增子序列长度。为什么要以“当前元素结尾”因为这样下一个元素只需要和当前结尾比较大小就能判断能否续上去。递归逻辑可以写成从头扫描所有j i如果nums[j] nums[i]那么nums[i]可以接在以nums[j]结尾的递增子序列后面所以当前答案是dfs(j) 1。在所有可行j中取最大值如果不存在更小的元素答案就是 1——只用自己单独形成一个子序列。from functools import lru_cache def lengthOfLIS(nums): n len(nums) lru_cache(None) def dfs(i): best 1 for j in range(i): if nums[j] nums[i]: best max(best, dfs(j) 1) return best return max(dfs(i) for i in range(n)) print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 输出 4改写成自底向上的递推就非常直观dp[i]表示以nums[i]结尾的 LIS 长度初始值为 1。对所有j i如果nums[j] nums[i]就用dp[j] 1更新dp[i]def lengthOfLIS(nums): 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) print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 输出 4这段代码的时间复杂度是O(n^2)对于 LeetCode 300 题足够通过。你可能会看到网上还有二分优化到O(n log n)的写法但那个版本的思路和递归推导关系不大更像是“维护一个递增的 tails 数组”。建议先把O(n^2)的版本写熟因为它能帮你建立“以某个位置结尾”的建模习惯。后面做“俄罗斯套娃信封问题”这类二维 LIS 时会发现基础的状态定义一变代码很快就能模仿出来。LIS 也提醒我们注意一个问题并不是所有 DP 的答案都在最后一个状态。爬楼梯的答案是dp[n]因为最终状态天然就是最后一次台阶LIS 的答案却在max(dp)因为最长递增子序列可能以任意位置结尾。所以每道题写完递推后都应该回到状态定义确认题目问的到底落在哪个格子上。6. 最长公共子序列 LCS两个序列的状态怎么定LCS 是动态规划里非常经典的双序列模型代表问题是 LeetCode 第 1143 题“最长公共子序列”。给定两个字符串text1和text2返回它们的最长公共子序列长度。子序列同样不要求连续但字符顺序要保持一致。双序列问题的状态定义一般套路是“同时考虑两个字符串的前缀”。设dfs(i, j)表示text1前i个字符和text2前j个字符的最长公共子序列长度。这里i和j表示长度而不是下标所以允许为 0。使用长度而不是下标的好处是边界更容易表示只要有一个字符串长度为 0公共子序列长度必然是 0。递归主体的判断要看两个字符串的第i个和第j个字符是否相等。如果text1[i - 1] text2[j - 1]说明这个字符可以成为公共子序列的最后一个字符于是结果等于dfs(i - 1, j - 1) 1。如果不相等那么这两个字符不可能同时作为公共子序列的末尾答案要从两种“放弃一个字符”的情况里取最大值要么放弃text1的最后一个字符即dfs(i - 1, j)要么放弃text2的最后一个字符即dfs(i, j - 1)。from functools import lru_cache def longestCommonSubsequence(text1, text2): n1, n2 len(text1), len(text2) lru_cache(None) def dfs(i, j): if i 0 or j 0: return 0 if text1[i - 1] text2[j - 1]: return dfs(i - 1, j - 1) 1 return max(dfs(i - 1, j), dfs(i, j - 1)) return dfs(n1, n2) print(longestCommonSubsequence(abcde, ace)) # 输出 3上面的记忆化写法非常容易理解因为lru_cache自动帮我们把(i, j)的结果缓存下来。等你觉得这个递归逻辑已经完全没问题再把它翻译成二维dp表格def longestCommonSubsequence(text1, text2): n1, n2 len(text1), len(text2) dp [[0] * (n2 1) for _ in range(n1 1)] for i in range(1, n1 1): for j in range(1, n2 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[n1][n2] print(longestCommonSubsequence(abcde, ace)) # 输出 3二维表格的更新方向也很清晰每个格子的值依赖它的上方dp[i - 1][j]、左方dp[i][j - 1]和左上dp[i - 1][j - 1]。只要按i从小到大、j从小到大遍历所有依赖值都已经被算好不需要额外递归。这也是双序列 DP 的通用模式把两个序列的前缀长度作为二维状态字符是否相等决定转移方式。编辑距离、两个字符串的删除操作等题和 LCS 同属一个模型。区别只在于“不相等”时如何处理代价。所以你不需要对每道题单独背只要掌握“双序列前缀状态 相等/不相等分支”这个模板遇到这类题就有了稳定的入手点。7. 常见错误与排查方法学动态规划时新手最容易在下面几个地方反复出错。我把它们整理成一张排查表遇到问题可以直接按表格顺序检查问题现象可能原因排查方法解决思路结果比答案少很多状态定义不完整漏掉了关键维度打印 dp 表看是否有同样的容量/位置被错误覆盖回到递归函数检查参数是否能表示所有决策信息答案看起来偏大01 背包用了正序遍历容量打印每次更新后的数组观察一个物品是否被重复使用容量循环改为倒序递归版本超时缺少记忆化或者没有意识到重叠子问题画出递归树数重复节点加lru_cache或改递推结果总是 0边界条件或者 dp 数组初始化错误检查 base case 返回值回到状态定义验证最小规模输入数组访问越界递归里没有处理好i 0或i 0的出口用最小的n手动模拟统一把递归参数改为长度让 0 作为边界递推方向反了没有分清自顶向下和自底向上把一个状态依赖的子状态列出来看哪些先算从最小状态开始循环变种题不会做只背了模板没理解问题如何拆成子问题先写一个暴力递归不急着写 dp 数组先保证递归正确再优化排查动态规划代码有一个很实用的技巧写一个没有任何优化的递归版本再写一个记忆化版本最后写递推版本。三个版本的逻辑应该完全一致。如果递推版本答案和递归版本对不上说明问题出在“递归思想”到“递推循环”转换的某一环而不是算法模型本身。你可以先用小规模随机输入把递归版本当作标准答案和递推版本对拍。很多 LeetCode 题目的数据规模比较小这种对拍方法在本地跑非常快。调试时不要只盯着代码看一定要把 dp 表格打印出来。二维 DP 打印后你会发现格子和格子之间的更新关系非常清楚如果某个格子数据异常基本能一眼看出是状态转移分支写错了还是初始化错了。这个习惯值得长期保持因为动态规划题目从“看懂”到“写对”中间往往就差一张调试表。8. 小白刷 LeetCode 动态规划的实战路线下面给出一条循序渐进的学习路线适合从零基础开始刷动态规划。建议不要把 100 多道动态规划题都塞进同一周而是按模型切块。第一组一维简单 DP。先做爬楼梯、打家劫舍、使用最小花费爬楼梯。这三道题的核心状态都是dp[i]只需要考虑一个位置怎么从邻近位置转移过来。做完这一组你要能独立完成“先写递归再加缓存再写循环”的完整链路。第二组网格二维 DP。可以做不同路径和最小路径和。这两道题的状态是dp[i][j]分别表示到达某个格子时的方案数或最小代价。它们会强化行和列的遍历方向感也能帮你理解二维表格里每个格子的依赖来源。第三组背包 DP。从 01 背包开始然后做分割等和子集、目标和。分割等和子集是经典的“判断能否装满半个总和”目标和可以改写成“选一堆数凑出 target”。如果感觉困难先把 01 背包的一维数组代码写熟再套进去。第四组序列 DP。做最长递增子序列、最长连续递增序列、最长公共子序列、编辑距离。这些题的核心不是背模板而是理解“以 i 结尾”和“前 i 个字符”两种状态定义的区别。前者适合单序列问题后者适合双序列问题。第五组完全背包与计数问题。做零钱兑换和零钱兑换 II。零钱兑换是求最少硬币数零钱兑换 II 是求组合数。这两题最大的价值是帮你彻底搞懂“正序容量更新”和“逆序容量更新”带来的语义变化。每组题做完后回来看复盘。比如零钱兑换 II 和分割等和子集区别在于顺序是否敏感目标和和 01 背包的区别在于“选择所有数但正负符号不同”。如果你能用自己的话把这些题之间的关系说清楚说明你真的掌握了而不是记住了解法。9. 写在最后动态规划的学习顺序动态规划对新手最大的障碍不是数学基础不够也不是代码能力不行而是学习顺序错了。很多人的顺序是“先看状态转移方程再倒推状态定义”最后越看越乱。正确的顺序应该是反过来先有一个朴素的递归函数再看递归参数能抽象出什么状态最后才把这个过程整理成状态转移方程。以后做动态规划题可以试着逼自己走三个步骤第一步不查题解直接把暴力递归写出来第二步看看有没有重复计算能不能用lru_cache优化第三步再把递归改写成递推。这样做会慢一些但每道题都会让你理解得更深。等你递归写得足够熟练很多简单题甚至可以不经过缓存直接就能写出递推因为“从递归到递推”已经变成条件反射了。如果你之前一直靠背公式刷动态规划我建议你从今天开始换这种方法找一道做过的题目把递归版本补上。你会发现那道题并没有想象中那么难只是当初直接从中间开始看才把最简单的推导跳过了。这文章里的爬楼梯、01 背包、LIS、LCS 四个例子都可以作为练手材料建议收藏备用。
从递归推导动态规划：告别死记状态转移方程
动态规划恐怕是 LeetCode 上劝退率最高的一块。很多人一刷到“动态规划”四个字第一反应不是打开编辑器而是先去找题解里的状态转移方程抄下来套循环跑通然后松了一口气。可下次遇到一道同类型的新题状态定义稍微换一下又不会了。问题不在题目难度而在你从一开始就在背一个没有推导过程的公式。这篇文章想换一个训练思路不背状态转移方程而是从递归一步步把 DP 推出来。你会发现状态转移方程不是从天而降的公式而是你写的递归函数本身的“运行规律”。只要你会写递归能看出重复计算在哪里动态规划其实是被动得到的优化结果。文章会以爬楼梯、01 背包、LIS最长递增子序列、LCS最长公共子序列四个经典场景为例把同一套推导链路完整走一遍。适合这类读者DP 题只会套模板换个包装就不会已经刷过一部分 LeetCode 简单题但碰到中等的动态规划题就卡住或者你只是想搞清楚“递归、记忆化搜索、递推 DP 到底是什么关系”。这篇文章不是题解合集也不会让你背任何公式但读完以后你可以自己把状态转移方程写出来。1. 状态转移方程不是背出来的先想清楚这个问题先回答一个基础问题为什么状态转移方程难背因为绝大多数教材和题解默认你已经接受了“状态”这个概念。比如常用的写法dp[i]、dp[i][j]看起来短小精悍但它背后藏着三个问题i到底表示什么dp[i]的答案是怎么从更小的dp值堆出来的边界条件为什么是那样写如果你跳过递归推导直接盯着这行公式看等于把“因”和“果”一起摆在面前但中间的逻辑链条完全缺失。你今天能看懂明天换个条件照样不会。动态规划真正依赖的只有两个前提。第一个是最优子结构意思是原问题的最优解可以由子问题的最优解组合出来。比如爬楼梯到第n阶的总方法数等于到第n-1阶的方法数加第n-2阶的方法数因为最后一步要么跨一阶要么跨两阶。第二个是重叠子问题意思是求解过程中同一个子问题会被反复算很多次。爬楼梯的暴力递归会反复求dfs(3)、dfs(2)这就是重叠。理解了这两个前提之后动态规划的完整推导链就非常清楚了先写出能表达“原问题怎么拆成子问题”的递归函数再看递归树中是否有大量重复节点有重复再加缓存最后把带缓存的递归改写成从底层开始向上填表的循环。这个过程不需要灵感也不需要背诵只需要按顺序执行。你甚至可以把 DP 理解成递归的“缓存优化版本”只是这个缓存不再用字典而是写进了数组里。2. 从递归到 DP以爬楼梯为例子2.1 题目背景LeetCode 第 70 题爬楼梯是动态规划入门的首选。题目要求很直接每次可以爬 1 阶或 2 阶问爬到第n阶有多少种不同的方法。这个题如果直接用数学排列组合去算会很别扭但用递归来想就非常简单到第n阶的走法等于到第n-1阶的走法加上到第n-2阶的走法因为你最后一步只有这两种可能。2.2 先写一个最朴素的暴力递归不要一上来就写dp数组先写递归函数。递归函数天然能表达“从当前问题拆到子问题”的结构。下面是最直接的版本def climbStairs(n): if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这个代码能通过人脑模拟但在 LeetCode 上大概率超时。原因来自递归树求climbStairs(5)时要先求climbStairs(4)和climbStairs(3)求climbStairs(4)又要再求一次climbStairs(3)。也就是说climbStairs(3)被重复算了。当n越来越大重复节点的数量是指数级增长的。这就是动态规划里最核心的“重叠子问题”。2.3 加一个缓存记忆化搜索重复算很浪费那就直接把算过的结果存下来。Python 里可以用lru_cache非常轻松地完成这件事from functools import lru_cache def climbStairs(n): lru_cache(None) def dfs(i): if i 2: return i return dfs(i - 1) dfs(i - 2) return dfs(n)这里dfs(i)的定义是“爬到第i阶有多少种方法”。递归函数内部依然调用dfs(i - 1)和dfs(i - 2)但因为有缓存同样的i只会真正计算一次。时间复杂度从指数级降到了O(n)。这种写法有个名字叫“自顶向下动态规划”也叫记忆化搜索。对于入门者我建议你至少在前期强制自己先写这种递归版本。因为它和问题描述最接近不容易把状态定义搞反。很多人在二维 DP 里分不清dp[i][j]的i和j哪个是行、哪个是列就是因为直接从填表开始完全没有经历“递归函数参数即状态”这一步。其实递归函数dfs(i)里的参数i就是 DP 状态里的维度递归函数里选择的拆分方式就是状态转移方向的来源。2.4 把递归改写成递推 DP现在再来看递推版本你会发现一切都有迹可循。既然dfs(i) dfs(i - 1) dfs(i - 2)并且我们知道i 1时答案是 1i 2时答案是 2那么就可以从 1 往上填表def climbStairs(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]这里的dp[i]其实就是刚才递归函数里的dfs(i)dp[i] dp[i - 1] dp[i - 2]就是递归函数去掉返回逻辑后剩下的赋值语句。你不需要单独背状态转移方程因为你已经把递归函数原封不动地翻译成了循环。唯一的区别是递归是等结果需要时才向上层返回而递推是从最小问题开始按顺序把所有状态都算一遍。这个例子可以继续压缩空间因为每次只依赖前两个状态用两个变量滚动就可以。但那是优化阶段的动作不是推导阶段的动作。对于新手我建议前几道题老老实实写完整数组把表打出来看清楚每个格子是怎么被算出来的再谈优化。3. 动态规划通用推导五步法爬楼梯跑通之后可以把经验升华为一套通用步骤。以后做任何动态规划题都可以按下面五步走。第一步定义状态。问自己一个问题如果我写递归函数参数应该是什么这组参数就是状态的维度。比如爬楼梯是dfs(i)表示第i阶的答案背包通常是dfs(i, c)表示处理到第i个物品、剩余容量为c时的答案LIS 是dfs(i)表示以第i个位置元素结尾的答案。状态定义是整个动态规划里最不能省的一步它决定了后面所有代码的写法。第二步写暴力递归主体。把当前问题看成从某个选择集合里挑一个子问题。例如爬楼梯的最后一步可以选择跨一阶或两阶背包的当前物品可以选择拿或不拿LCS 的当前字符可以匹配或不匹配。这一步要写一个没有缓存的递归先不要担心性能只求逻辑正确。第三步找边界条件和返回值。边界条件就是递归的出口。爬楼梯是n 2直接返回背包是物品数量为负或容量为 0 时返回 0LIS 是只有一个元素时返回 1。边界别硬记要回到状态定义里推导想清楚“当参数最小的时候答案显然是多少”。第四步检查是否存在重叠子问题。在草稿纸上画出递归树观察同一个(i)或(i, c)是否被多个分支调用。如果没有重叠说明这个问题用普通分治或回溯就能解决如果有重叠才需要缓存也就是进入真正的动态规划。第五步把递归改写成递推。把递归函数里的“返回某个值”改成“把某个格子的值算出来”。递推方向一般和递归参数减小的方向相反。递归从大问题拆到小问题递推则从小问题开始累积到大问题。改写要同时确定两层循环的顺序这往往是背包类问题最容易出错的地方。其实这套流程就是很多教材里说的“状态定义 状态转移 边界条件 遍历顺序”但它的出现顺序是自然推导出来的不需要死记。为了让你看到这套方法的泛化能力下面三个经典模型都会按同样的路径走一遍。4. 背包问题从 01 背包开始背包问题在 LeetCode 里非常重要尤其是 01 背包和完全背包会演变成“分割等和子集”“目标和”“零钱兑换”等热门题。这里先用 01 背包讲透遍历顺序。题目模型是有n个物品第i个物品的重量是weights[i]价值是values[i]每个物品只能选一次背包总容量是capacity求能装下的最大总价值。第一步定义状态。我们需要同时知道“处理到哪个物品”和“当前剩余容量”所以递归函数有两个参数dfs(i, c)表示“从第 0 到第 i 个物品中做选择剩余容量为 c 时能获得的最大价值”。第二步写递归主体。对当前第i个物品只有两种选择不拿那么结果等于dfs(i - 1, c)拿那么需要先判断weights[i] c然后结果是dfs(i - 1, c - weights[i]) values[i]。取两者最大值即可。from functools import lru_cache def knapsack01(weights, values, capacity): n len(weights) lru_cache(None) def dfs(i, c): if i 0: return 0 if weights[i] c: return dfs(i - 1, c) return max(dfs(i - 1, c), dfs(i - 1, c - weights[i]) values[i]) return dfs(n - 1, capacity) print(knapsack01([1, 3, 4], [15, 20, 30], 4)) # 输出 35这里用i 0作为递归出口表示没有物品可选时价值为 0。dfs(i - 1, c - weights[i])里的i - 1保证了每个物品最多被选一次因为一旦拿走当前物品后面的递归只会继续往前面的物品选择不会再回头拿自己。这个细节是 01 背包和完全背包的本质区别。第三步改写成二维递推 DP。把递归参数映射成数组下标dp[i][c]表示“前 i 个物品容量为 c”时的最大价值。这里让i从 1 到n对应物品下标i-1从而让dp[0][c] 0作为没有物品时的边界。def knapsack01(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for c in range(capacity 1): if weights[i - 1] c: dp[i][c] dp[i - 1][c] else: dp[i][c] max( dp[i - 1][c], dp[i - 1][c - weights[i - 1]] values[i - 1] ) return dp[n][capacity] print(knapsack01([1, 3, 4], [15, 20, 30], 4)) # 输出 35二维版本虽然空间大一点但逻辑和递归完全一致适合用来验证理解。当你发现dp[i]这一行只依赖dp[i-1]那一行时就可以尝试用一维数组滚动更新def knapsack01(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): # 必须倒序遍历容量防止同一个物品被选多次 for c in range(capacity, weights[i] - 1, -1): dp[c] max(dp[c], dp[c - weights[i]] values[i]) return dp[capacity] print(knapsack01([1, 3, 4], [15, 20, 30], 4)) # 输出 35这段代码里最容易踩的坑就是内层容量循环的顺序。为什么必须倒序因为一维数组里没有“行号”可以区分当前物品是否已经被更新。如果正序遍历容量那么计算大容量dp[c]时会用到刚刚被当前物品更新过的dp[c - weights[i]]这相当于同一个物品已经在前面容量较小的状态里被放入过一次再放一次就变成一个物品可以无限使用的完全背包了。倒序遍历保证每个容量只使用上一轮旧数据符合 01 背包“每件物品只能选一次”的约束。建议你亲手跑一遍这个例子把每次更新后的dp数组打印出来。你会发现倒序时第i个物品产生的影响只向右推进一次改成顺序时一个物品的价值会在同一轮里不断叠加。看明白了这一点背包变种题就再也不会被遍历顺序卡住。5. 最长递增子序列 LIS子序列问题的入门模型LIS 是 LeetCode 上另一类经典动态规划题代表问题是“最长递增子序列”。注意子序列不要求连续但元素之间的相对顺序必须保持。比如nums [10, 9, 2, 5, 3, 7, 101, 18]的最长递增子序列长度是 4一个答案是[2, 3, 7, 101]。这道题很多人的第一反应是“枚举所有起点”但很快会发现很难判断后续元素是否递增。更自然的状态定义是dfs(i)表示以nums[i]这个元素结尾的最长递增子序列长度。为什么要以“当前元素结尾”因为这样下一个元素只需要和当前结尾比较大小就能判断能否续上去。递归逻辑可以写成从头扫描所有j i如果nums[j] nums[i]那么nums[i]可以接在以nums[j]结尾的递增子序列后面所以当前答案是dfs(j) 1。在所有可行j中取最大值如果不存在更小的元素答案就是 1——只用自己单独形成一个子序列。from functools import lru_cache def lengthOfLIS(nums): n len(nums) lru_cache(None) def dfs(i): best 1 for j in range(i): if nums[j] nums[i]: best max(best, dfs(j) 1) return best return max(dfs(i) for i in range(n)) print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 输出 4改写成自底向上的递推就非常直观dp[i]表示以nums[i]结尾的 LIS 长度初始值为 1。对所有j i如果nums[j] nums[i]就用dp[j] 1更新dp[i]def lengthOfLIS(nums): 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) print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 输出 4这段代码的时间复杂度是O(n^2)对于 LeetCode 300 题足够通过。你可能会看到网上还有二分优化到O(n log n)的写法但那个版本的思路和递归推导关系不大更像是“维护一个递增的 tails 数组”。建议先把O(n^2)的版本写熟因为它能帮你建立“以某个位置结尾”的建模习惯。后面做“俄罗斯套娃信封问题”这类二维 LIS 时会发现基础的状态定义一变代码很快就能模仿出来。LIS 也提醒我们注意一个问题并不是所有 DP 的答案都在最后一个状态。爬楼梯的答案是dp[n]因为最终状态天然就是最后一次台阶LIS 的答案却在max(dp)因为最长递增子序列可能以任意位置结尾。所以每道题写完递推后都应该回到状态定义确认题目问的到底落在哪个格子上。6. 最长公共子序列 LCS两个序列的状态怎么定LCS 是动态规划里非常经典的双序列模型代表问题是 LeetCode 第 1143 题“最长公共子序列”。给定两个字符串text1和text2返回它们的最长公共子序列长度。子序列同样不要求连续但字符顺序要保持一致。双序列问题的状态定义一般套路是“同时考虑两个字符串的前缀”。设dfs(i, j)表示text1前i个字符和text2前j个字符的最长公共子序列长度。这里i和j表示长度而不是下标所以允许为 0。使用长度而不是下标的好处是边界更容易表示只要有一个字符串长度为 0公共子序列长度必然是 0。递归主体的判断要看两个字符串的第i个和第j个字符是否相等。如果text1[i - 1] text2[j - 1]说明这个字符可以成为公共子序列的最后一个字符于是结果等于dfs(i - 1, j - 1) 1。如果不相等那么这两个字符不可能同时作为公共子序列的末尾答案要从两种“放弃一个字符”的情况里取最大值要么放弃text1的最后一个字符即dfs(i - 1, j)要么放弃text2的最后一个字符即dfs(i, j - 1)。from functools import lru_cache def longestCommonSubsequence(text1, text2): n1, n2 len(text1), len(text2) lru_cache(None) def dfs(i, j): if i 0 or j 0: return 0 if text1[i - 1] text2[j - 1]: return dfs(i - 1, j - 1) 1 return max(dfs(i - 1, j), dfs(i, j - 1)) return dfs(n1, n2) print(longestCommonSubsequence(abcde, ace)) # 输出 3上面的记忆化写法非常容易理解因为lru_cache自动帮我们把(i, j)的结果缓存下来。等你觉得这个递归逻辑已经完全没问题再把它翻译成二维dp表格def longestCommonSubsequence(text1, text2): n1, n2 len(text1), len(text2) dp [[0] * (n2 1) for _ in range(n1 1)] for i in range(1, n1 1): for j in range(1, n2 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[n1][n2] print(longestCommonSubsequence(abcde, ace)) # 输出 3二维表格的更新方向也很清晰每个格子的值依赖它的上方dp[i - 1][j]、左方dp[i][j - 1]和左上dp[i - 1][j - 1]。只要按i从小到大、j从小到大遍历所有依赖值都已经被算好不需要额外递归。这也是双序列 DP 的通用模式把两个序列的前缀长度作为二维状态字符是否相等决定转移方式。编辑距离、两个字符串的删除操作等题和 LCS 同属一个模型。区别只在于“不相等”时如何处理代价。所以你不需要对每道题单独背只要掌握“双序列前缀状态 相等/不相等分支”这个模板遇到这类题就有了稳定的入手点。7. 常见错误与排查方法学动态规划时新手最容易在下面几个地方反复出错。我把它们整理成一张排查表遇到问题可以直接按表格顺序检查问题现象可能原因排查方法解决思路结果比答案少很多状态定义不完整漏掉了关键维度打印 dp 表看是否有同样的容量/位置被错误覆盖回到递归函数检查参数是否能表示所有决策信息答案看起来偏大01 背包用了正序遍历容量打印每次更新后的数组观察一个物品是否被重复使用容量循环改为倒序递归版本超时缺少记忆化或者没有意识到重叠子问题画出递归树数重复节点加lru_cache或改递推结果总是 0边界条件或者 dp 数组初始化错误检查 base case 返回值回到状态定义验证最小规模输入数组访问越界递归里没有处理好i 0或i 0的出口用最小的n手动模拟统一把递归参数改为长度让 0 作为边界递推方向反了没有分清自顶向下和自底向上把一个状态依赖的子状态列出来看哪些先算从最小状态开始循环变种题不会做只背了模板没理解问题如何拆成子问题先写一个暴力递归不急着写 dp 数组先保证递归正确再优化排查动态规划代码有一个很实用的技巧写一个没有任何优化的递归版本再写一个记忆化版本最后写递推版本。三个版本的逻辑应该完全一致。如果递推版本答案和递归版本对不上说明问题出在“递归思想”到“递推循环”转换的某一环而不是算法模型本身。你可以先用小规模随机输入把递归版本当作标准答案和递推版本对拍。很多 LeetCode 题目的数据规模比较小这种对拍方法在本地跑非常快。调试时不要只盯着代码看一定要把 dp 表格打印出来。二维 DP 打印后你会发现格子和格子之间的更新关系非常清楚如果某个格子数据异常基本能一眼看出是状态转移分支写错了还是初始化错了。这个习惯值得长期保持因为动态规划题目从“看懂”到“写对”中间往往就差一张调试表。8. 小白刷 LeetCode 动态规划的实战路线下面给出一条循序渐进的学习路线适合从零基础开始刷动态规划。建议不要把 100 多道动态规划题都塞进同一周而是按模型切块。第一组一维简单 DP。先做爬楼梯、打家劫舍、使用最小花费爬楼梯。这三道题的核心状态都是dp[i]只需要考虑一个位置怎么从邻近位置转移过来。做完这一组你要能独立完成“先写递归再加缓存再写循环”的完整链路。第二组网格二维 DP。可以做不同路径和最小路径和。这两道题的状态是dp[i][j]分别表示到达某个格子时的方案数或最小代价。它们会强化行和列的遍历方向感也能帮你理解二维表格里每个格子的依赖来源。第三组背包 DP。从 01 背包开始然后做分割等和子集、目标和。分割等和子集是经典的“判断能否装满半个总和”目标和可以改写成“选一堆数凑出 target”。如果感觉困难先把 01 背包的一维数组代码写熟再套进去。第四组序列 DP。做最长递增子序列、最长连续递增序列、最长公共子序列、编辑距离。这些题的核心不是背模板而是理解“以 i 结尾”和“前 i 个字符”两种状态定义的区别。前者适合单序列问题后者适合双序列问题。第五组完全背包与计数问题。做零钱兑换和零钱兑换 II。零钱兑换是求最少硬币数零钱兑换 II 是求组合数。这两题最大的价值是帮你彻底搞懂“正序容量更新”和“逆序容量更新”带来的语义变化。每组题做完后回来看复盘。比如零钱兑换 II 和分割等和子集区别在于顺序是否敏感目标和和 01 背包的区别在于“选择所有数但正负符号不同”。如果你能用自己的话把这些题之间的关系说清楚说明你真的掌握了而不是记住了解法。9. 写在最后动态规划的学习顺序动态规划对新手最大的障碍不是数学基础不够也不是代码能力不行而是学习顺序错了。很多人的顺序是“先看状态转移方程再倒推状态定义”最后越看越乱。正确的顺序应该是反过来先有一个朴素的递归函数再看递归参数能抽象出什么状态最后才把这个过程整理成状态转移方程。以后做动态规划题可以试着逼自己走三个步骤第一步不查题解直接把暴力递归写出来第二步看看有没有重复计算能不能用lru_cache优化第三步再把递归改写成递推。这样做会慢一些但每道题都会让你理解得更深。等你递归写得足够熟练很多简单题甚至可以不经过缓存直接就能写出递推因为“从递归到递推”已经变成条件反射了。如果你之前一直靠背公式刷动态规划我建议你从今天开始换这种方法找一道做过的题目把递归版本补上。你会发现那道题并没有想象中那么难只是当初直接从中间开始看才把最简单的推导跳过了。这文章里的爬楼梯、01 背包、LIS、LCS 四个例子都可以作为练手材料建议收藏备用。 
