小白第一次在 LeetCode 上刷到动态规划题时最常见的反应不是“这题有意思”而是“题解在说什么”。很多人看完状态定义、转移方程、初始化之后觉得自己懂了合上题解自己写立刻卡在第一步为什么dp[i]要这么定义为什么转移是dp[i - 1] dp[i - 2]为什么有些题先遍历物品有些题先遍历容量这个问题的根源不是理解力不够而是把动态规划学成了“背公式”。状态转移方程是建模完成之后自然长出来的结论不是需要背的起点。真正重要的工作发生在写方程之前把题目还原成递归看递归树里有没有重复子问题再把重复计算用缓存消掉最后把缓存从“往下传”改成“从底往上填”。这篇内容按这套思路展开。先从一个最小例子说明“递归 - 记忆化搜索 - 迭代 DP”的完整链路然后落地到 0-1 背包、LIS、LCS 三类 LeetCode 高频题型。思路适用于 LeetCode 上的大量动态规划题不只是某一道题。示例基于 Python 3读 C、Java 的读者按语法翻译即可核心推理过程完全一致。1. 动态规划难在哪状态转移方程只是“结论”不是“起点”很多人学习动态规划的顺序是反的先看状态定义再看转移方程再看初始化然后试图记住整个套路。问题是 LeetCode 不会只考原题它会在物品选择、容量限制、序列顺序、字符串长度上做各种变化。死背的方程稍微换个外壳就失效了。1.1 只背方程的后果能看懂题解独立做题还是卡住看一下常见的题解写法dp[i] 表示以 nums[i] 结尾的最长递增子序列长度 转移dp[i] max(dp[i], dp[j] 1)其中 j i 且 nums[j] nums[i]这句话本身没有错但它少交代了一个关键问题为什么状态要定义成“以 nums[i] 结尾”而不是“前 i 个数里的最长递增子序列”如果读者没有回答这个问题就只能靠记忆硬套题目变成“最长递减子序列”“最长摆动子序列”时第一反应仍然是找答案而不是自己推导。一个更靠谱的学习顺序是先尝试用递归描述原问题。画出递归树观察是否有大量重复子问题。加一个缓存数组得到记忆化搜索。把缓存数组改成自底向上的迭代填表得到标准的 DP 方案。这样得到的“状态转移方程”其实是第 3、4 步自然产生的。哪怕之后忘了公式也能从递归重新推出来。1.2 真正可复用的流程暴力递归、记忆化搜索、迭代 DP用一张表概括三种写法的关系写法核心数据结构复杂度来源主要优势主要代价暴力递归调用栈 参数子问题被反复展开思路最直接最容易验证题意存在大量重复计算容易超时记忆化搜索调用栈 缓存容器每个子问题只算一次保留递归思路性能接近 DP依赖递归深度状态极多时可能栈溢出迭代 DP数组/多维数组按顺序填表无递归栈压力可做空间优化需要事先确定遍历顺序和边界含义对新手来说暴力递归是“翻译题意”的过程记忆化搜索是“优化速度”的过程迭代 DP 是“换一种执行方式”的过程。这三步不是互相独立的三种解法而是同一个思路的三种形态。1.3 先判断题目适不适合动态规划看递归树看重复子问题不是所有题都要用 DP。适合 DP 的题目通常有两个特征原问题可以拆成更小的同类问题。拆开后的子问题会重复出现。例如“爬楼梯”要算第 n 层的方案数递归展开时会反复算第 3 层、第 2 层的方案这些子问题重复出现符合 DP 的使用前提。如果某道题的子问题完全独立例如快速排序每次切分后处理两个互不相干的区间那就谈不上“重复子问题”也不太需要 DP 缓存。第二个重要特征是“无后效性”。大白话说就是当前层的结果一旦算出来后续计算只依赖这个结果值不再关心它是通过哪条路径算出来的。比如“从第 1 层爬到第 5 层有多少种方式”只需要知道第 4 层和第 3 层的方案数不需要关心那些方案具体怎么走。这样就能放心地用子问题结果组合成父问题结果。注意不要把“能递归”和“适合 DP”划等号。只有递归树中存在重叠子问题时加缓存才有收益子问题完全不重叠的递归直接用普通递归或循环处理即可。2. 用爬楼梯证明dp[i] 是把递归结果按顺序存起来LeetCode 第 70 题“爬楼梯”是理解和验证动态规划的最小样本。题目说一次可以爬 1 层或 2 层问爬到第 n 层有多少种不同方法。2.1 暴力递归先写出与原题一致的子问题爬到第 n 层的最后一步只能来自第 n-1 层再爬 1 层或者来自第 n-2 层再爬 2 层。因此f(n) f(n - 1) f(n - 2)这其实已经是转移方程了但它首先是递归定义。写成暴力递归def climb_stairs_recursive(n: int) - int: if n 1: return 1 if n 2: return 2 return climb_stairs_recursive(n - 1) climb_stairs_recursive(n - 2)运行climb_stairs_recursive(5)调用过程会展开成一棵递归树。f(3)会被f(5)和f(4)重复计算f(2)会更多次重复计算。n 稍大比如 n40重复计算量会指数增长本地运行会明显卡顿线上提交会超时。这里要注意递归边界。n 1返回 1 只爬 1 层n 2返回 2 表示“11”和“2”两种方法。不定义f(0)避免一开始就让新手纠结“爬到第 0 层有几种方法”这种歧义问题。2.2 记忆化递归里的重复计算被缓存后就具备 DP 的雏形给上面的递归加一个缓存数组同一个参数只算一次def climb_stairs_memo(n: int) - int: memo [-1] * (n 1) def dfs(x: int) - int: if x 1: return 1 if x 2: return 2 if memo[x] ! -1: return memo[x] memo[x] dfs(x - 1) dfs(x - 2) return memo[x] return dfs(n)这段代码保留了递归的思考方式但每个x只展开一次。dfs(x)执行完结果存入memo[x]之后再被调用时直接从缓存读取。记忆化搜索和迭代 DP 的信息量已经等价。memo[x]的含义就是“爬到第 x 层有多少种方法”后续迭代 DP 里的dp[x]也只是换成循环去填同一个数组。2.3 把 memo 顺序反过来就得到 dp[i]递归的方向是从上往下想知道f(n)先要知道f(n-1)和f(n-2)。如果把顺序倒过来从 n1、n2 出发依次往后算就是自底向上的迭代 DPdef climb_stairs_dp(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] dp[i - 1] dp[i - 2]但它的来源在递归已经解释过最后一步从第i-1层爬 1 层或者从第i-2层爬 2 层。如果只要求最终答案还能把一维数组压缩成两个临时变量。这里不急着优化先把“数组版的递归”看懂更重要。2.4 三种写法怎么验证递推边界为什么不能乱改在本地验证时可以写一个极小的脚本依次比较三种写法的结果for n in range(1, 15): a climb_stairs_recursive(n) b climb_stairs_memo(n) c climb_stairs_dp(n) assert a b c, (n, a, b, c) print(ok)递归版算到 n30 或 n40 时会明显变慢这正是“重复子问题导致指数级开销”的直观证据。验证时能立刻感受到加缓存前后差距比单纯背复杂度分析更有记忆点。边界这块最容易踩坑的是dp[0]。很多题解写dp[1]1; dp[2]2也有的写dp[0]1; dp[1]1两种写法的斐波那契下标不一致。对 LeetCode 的爬楼梯题n 1直接初始化dp[1] 1、dp[2] 2最少歧义。如果以后遇到“斐波那契数列”题再看它从第 0 项还是第 1 项开始不是所有 DP 题的 0 都必须等于某种语义。注意做 DP 题时初始化值要从原题含义推导不要为了凑公式乱设dp[0]。dp[0]1在别的场景可能完全错误。3. 从一个最小例子提炼四步法状态、决策、初始化、遍历顺序爬楼梯只是热身。它的意义不只是学会一道题而是提炼出一个能套用到背包、LIS、LCS 的通用建模顺序。3.1 状态定义看递归函数的参数不用临场编很多新手最大的障碍是“怎么想到 dp[i] 定义成这个意思”。一个可复制的技巧是先写递归递归函数的参数是什么DP 的状态维度通常就是什么。比如爬楼梯的递归函数def dfs(x: int) - int: ...参数只有一个xDP 就是一维数组。dp[x]与dfs(x)含义一致都是“爬 x 层有多少种方法”。再看 0-1 背包如果递归写成def dfs(i: int, capacity_left: int) - int: ...参数有两个当前物品下标i、剩余容量capacity_leftDP 就需要二维数组dp[i][j]。字符串问题常常有两个指针参数因此二维 DP。所以状态定义不是靠灵感而是跟着递归的参数走。3.2 转移方程写出“最后一步有哪些选择”转移方程的本质是回答“一个子问题如何由更小的子问题组合出来”。在爬楼梯里最后一步是爬 1 层或 2 层在背包里最后一个物品是“选”或“不选”在递增子序列里当前数字要么自己单独成序列要么接在某个更小的数字后面。不背公式的写法是先描述“到达这个状态之前发生了什么”然后把这些分支相加或取最大/最小值。建议用中文先写一两句话再翻译成代码。爬山 x 层的方法数 - 先爬到 x-1 层再爬 1 层 - 先爬到 x-2 层再爬 2 层 所以f(x) f(x-1) f(x-2)如果中文分支写不出来说明还没有理解题意这时候写代码大概率也是错的。3.3 初始化对应递归的边界不要硬凑 dp[0]初始化就是递归里那些不再拆分的边界情况。递归边界写成if x 1: return 1自底向上 DP 就该有dp[1] 1。递归边界使用n 2时初始化也要包含dp[2] 2。初始化一旦和递归边界脱节要么数组越界要么前几个值算错。建议在写迭代 DP 前先完整写一版记忆化搜索。记忆化搜索里的终止条件写清楚了迭代 DP 的初始化就不容易出错。很多新手迭代 DP 写不好而且说不清为什么就是因为跳过了这一步。3.4 遍历顺序保证 dp[i] 用到的值都已经算好一维 DP 的遍历顺序通常很直观从前往后循环即可。二维 DP 需要分析状态依赖的方向。例如爬楼梯dp[i] dp[i - 1] dp[i - 2]dp[i]依赖更小的i所以从小到大循环。如果从大往小循环dp[i-1]还没算出来结果就是脏数据。如果一道题有两种不同遍历顺序的写法例如背包题里先遍历物品还是先遍历容量要回到转移方程判断dp[i][j]依赖的是哪一行、哪一列。下面第 4 节会解释这个具体例子。3.5 写题卡住时回到小样例人工填表有一个检查手段非常朴素但很有效找一个小输入用手在纸上模拟几轮。LeetCode 不会提供交互式调试但在本地编辑器里可以临时加 print。填完一个 3x4 的小表后状态定义和下标的正确性通常立刻就能看出来。这比反复读题解更接近“自己会做”。4. 0-1 背包从“选或不选”到二维表再到一维滚动背包问题并不是一道原始 LeetCode 题而是一类经典问题。LeetCode 上的“分割等和子集”“目标和”“最后一块石头的重量 II”等本质都能归约到 0-1 背包。理解这一节之后再去做这类题目会轻松很多。4.1 用一个 4 行的小样例把问题钉死先给一个固定输入所有代码都围绕它验证物品重量weight [2, 1, 3] 物品价值value [4, 2, 3] 背包容量capacity 4每个物品最多选一次目标是在不超过背包容量的前提下使总价值最大。如果只贪心选单位价值最高的“物品 1”重量 2、价值 4剩余容量 2 不能放重量 3 的物品如果选物品 2重量 1、价值 2和物品 3重量 3、价值 3总重量 4总价值 5如果选物品 1 和物品 2总重量 3总价值 6这是最优答案。后面所有 DP 推导都以这套小样例为准。4.2 先写递归再理解二维 DP 为什么要这么定义递归思路当前正在处理下标为i的物品剩余容量为c。可以从两个方向思考如果第i个物品的重量超过c不能选它结果等于处理下一个物品。如果能选要比较“不选它”和“选它”哪个价值更大。写成递归def knapsack_recursive(weight, value, i, c): if i len(weight): return 0 if weight[i] c: return knapsack_recursive(weight, value, i 1, c) not_take knapsack_recursive(weight, value, i 1, c) take value[i] knapsack_recursive(weight, value, i 1, c - weight[i]) return max(not_take, take) weight [2, 1, 3] value [4, 2, 3] print(knapsack_recursive(weight, value, 0, 4))把递归参数中的“当前物品下标i”和“剩余容量c”作为缓存维度加一个二维 memo就是记忆化搜索解法。这部分确认无歧义之后再转向二维 dp 数组。常见的背包 DP 状态定义是dp[i][j]只考虑前i个物品时背包容量为j能获得的最大价值。这里的i表示“物品下标从 0 到 i-1 已经考虑完”和递归里从i往后考虑的方向相反但转移的本质一样。4.3 动态规划表是怎么填出来的为了和前面的递归方向统一先写一个用下标从0..i-1的二维版本def knapsack_dp(weight, value, capacity): n len(weight) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w weight[i - 1] v value[i - 1] for j in range(capacity 1): if w j: dp[i][j] dp[i - 1][j] else: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) return dp[n][capacity] print(knapsack_dp([2, 1, 3], [4, 2, 3], 4))用小样例填表可以得到这样的dp结果。行表示只考虑前 i 个物品列表示背包容量 ji \ j01234000000100444202466302466为什么第 3 行 i3 时容量 4 的值仍是 6因为第 3 个物品重量为 3、价值为 3如果选它前两个物品在容量 1 下的最大价值为 2合计 5如果不选它前两个物品在容量 4 下的最大价值为 6所以取最大值仍为 6。填表顺序是从上到下、从左到右因为dp[i]只依赖dp[i-1]。4.4 空间优化内层倒序遍历才能保证每个物品只选一次仔细观察转移dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v)新一行其实只依赖上一行的值因此可以用一维数组反复滚动覆盖。一维版本常见写法是def knapsack_dp_1d(weight, value, capacity): n len(weight) dp [0] * (capacity 1) for i in range(n): w weight[i] v value[i] for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity] print(knapsack_dp_1d([2, 1, 3], [4, 2, 3], 4))一维dp[j]表示“当前已经处理过的物品集合下容量为 j 的最大价值”。内层循环必须从大到小是因为如果j从小到大dp[j - w]可能已经在这一次物品循环中被更新过了。举一个反例只有一个物品 w2,v4容量 j 从 0 到 4 正序更新时j 2: dp[2] max(dp[2], dp[0] 4) 4 j 4: dp[4] max(dp[4], dp[2] 4) 8算到 j4 时使用的dp[2]是已经放过该物品后的dp[2]于是同一个物品被放了两次这就不符合 0-1 背包的“每件物品最多选一次”。倒序从 j4 到 j2 时dp[2]还没有被当前物品更新过状态仍是旧值因此只能选一次。注意一维滚动数组的内层循环顺序不是细节问题。0-1 背包必须倒序如果采用正序代码就变成了“完全背包”的允许重复选择逻辑。4.5 背包题常见的 3 个边界坑坑点错误现象原因正确做法容量循环写反答案偏大或物品被重复选一维优化后内层正序遍历旧状态被覆盖内层for j in range(capacity, w - 1, -1)重量大于容量时直接取dp[i-1][j-w]下标越界或得到负数索引的错误值没有判断w j先判断物品能否放入当前容量容量初始化全部为 0当题目要求“恰好装满”时结果错误“不超过容量”和“恰好装满”语义不同恰好装满时dp[0]0其余初始化成-inf在 LeetCode 背包变体里最常出现的是第三种初始化陷阱。例如“分割等和子集”要求能不能把数组分成两个和相等的子集等价于能否选出一部分数字使总和等于sum/2不是找“不超过目标的最大值”。理解 0-1 背包后再研究这类变体会更容易。5. LIS 最长递增子序列dp[i] 的含义决定转移条件LeetCode 第 300 题“最长递增子序列”是另一个经典模型。给定数组nums [10, 9, 2, 5, 3, 7, 101, 18]最长递增子序列是[2, 3, 7, 18]或[2, 5, 7, 101]长度是 4。子序列不要求连续只要求保持原数组中的相对顺序。5.1 为什么不能用连续子数组的思路“子数组”要求连续所以用滑动窗口能解决。而“子序列”允许中间跳过元素窗口类算法解不了。递归思路必须显式考虑“当前数字能不能接在之前某个数字后面”。一个容易犯的错误是只比较相邻元素认为dp[i] dp[i-1] 1或dp[i] 1。这种写法只能处理连续上升段无法处理[2, 5, 3, 7]这类中间断开的序列。5.2 从递归视角推导 LIS 的状态定义先看最后一个元素。以nums[i]结尾的最长递增子序列可以分成两类单独一个数字长度是 1。接在某个nums[j]后面条件是j i且nums[j] nums[i]此时长度是dp[j] 1。因此状态定义突出关键词“以 nums[i] 结尾”。这样定义的意义在于如果要让nums[i]接在nums[j]后面那么子问题dp[j]必须也知道自己的结尾是谁否则无法判断nums[i]能否接上。递归表达def length_of_lis_ending_at(nums, i): if i 0: return 1 best 1 for j in range(i): if nums[j] nums[i]: best max(best, length_of_lis_ending_at(nums, j) 1) return best这段递归对应二维遍历但缓存切片就是dp。5.3 O(n^2) 的动态规划实现标准解法用双层循环def length_of_lis(nums) - int: if not nums: return 0 n len(nums) dp [1] * n ans 1 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) ans max(ans, dp[i]) return ans print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))用题目中的例子填表inums[i]能与前面的哪些 j 拼接dp[i]010无119无122无135j2 处 nums2dp[2]1243j2 处 nums2dp[2]1257j2、3、4max(11, 21, 21)36101j0..5 都可max(..., 31)4718j2、3、4、54最终答案不是dp[n - 1]而是所有dp[i]中的最大值。因为以倒数第一个数字结尾的子序列未必是全数组最长递增子序列。5.4 一个容易踩的坑更新答案的位置有些新手会写成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 dp[n - 1]当nums是降序或整体上升趋势被最后一个元素破坏时dp[n-1]不是全局最大值。正确做法是在每次算出dp[i]后同步维护ans或最后返回max(dp)。另一个坑是修改递增条件。LeetCode 第 300 题要求严格递增因此条件是nums[j] nums[i]。如果题目允许相等元素形成递增序列例如“最长非降子序列”才需要写成。不要凭印象统一处理。6. LCS 最长公共子序列二维 DP 的匹配与忽略LeetCode 第 1143 题“最长公共子序列”让很多二维 DP 新手第一次接触“匹配 / 不匹配”的分支。给定两个字符串text1 abcde、text2 ace最长公共子序列是ace长度为 3。6.1 递归分析两个字符串的最后一个字符对于两个字符串最自然的子问题是“看最后一个字符”。如果text1[i] text2[j]说明这两个字符可以成为公共子序列的一部分结果等于各自去掉最后一个字符后的子问题再加 1。如果不等公共子序列不可能同时以这两个字符结尾因此要比较两个分支去掉text1的最后一个字符或者去掉text2的最后一个字符取较大者。递归定义def lcs_recursive(s1, s2, i, j): if i 0 or j 0: return 0 if s1[i] s2[j]: return lcs_recursive(s1, s2, i - 1, j - 1) 1 return max( lcs_recursive(s1, s2, i - 1, j), lcs_recursive(s1, s2, i, j - 1) )这个递归直接把状态维度定位成i和jDP 自然就是二维数组。6.2 填表过程与完整代码自底向上的二维 DP 用dp[i][j]表示“text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度”。下标从 1 开始这样dp[0][j] 0和dp[i][0] 0正好对应空字符串情况不需要额外判断。def longest_common_subsequence(text1: str, text2: str) - int: n, m len(text1), len(text2) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 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[n][m] print(longest_common_subsequence(abcde, ace))以text1 abcde为行、text2 ace为列最终表如下dpace0000a0111b0111c0122d0122e0123每个格子要么来自左上角加 1要么来自上方或左方取最大值。这种依赖关系也决定了遍历顺序行从上到下列从左到右保证每个格子计算前其上方、左方、左上方的值都已就绪。6.3 为什么两个字符不等时要取 max 而不是加 1如果当前两个字符不相等不能把它们强行加入公共子序列。此时最长公共子序列不会同时使用这两个字符只能从“text1 去掉当前字符”或“text2 去掉当前字符”的结果中选一个更长的。很多新手在这里写成dp[i][j] dp[i - 1][j - 1]这会丢掉可能的中间结果。比如text1 abc、text2 ac处理到b和c不等时如果直接继承左上方dp[1][1]1会漏掉ac这条长度为 2 的公共子序列。取max(dp[2][2], dp[1][3])才能保留正确长度。6.4 打印一个 LCS 结果的回溯写法只输出长度通常不够。面试或实际场景里可能还要输出一个具体的公共子序列。回溯思路是从右下角往左上走如果text1[i-1] text2[j-1]说明这个字符来自dp[i-1][j-1] 1记录它然后向左上走。如果不相等比较dp[i-1][j]和dp[i][j-1]哪个大就往哪个方向走因为它们才是当前格子的来源。如果两边相等任选一边即可但注意可能对应不同的公共子序列。def lcs_with_path(text1: str, text2: str) - str: n, m len(text1), len(text2) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 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]) result [] i, j n, m while i 0 and j 0: if text1[i - 1] text2[j - 1]: result.append(text1[i - 1]) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: i - 1 else: j - 1 return .join(reversed(result)) print(lcs_with_path(abcde, ace))这里有个常见坑回溯过程中先把字符加入列表最后得到的是逆序字符串一定要reversed或倒序拼接。另外dp[i-1][j] dp[i][j-1]时会向上走这会导致存在多个最优解时只输出其中一个但长度一定是对的。7. LeetCode 动态规划题的调试和复盘先会打印 DP 表再谈优化写动态规划题时最忌讳的是提交失败后盯着代码反复改却不知道状态表长什么样。早一点学会打印、检查、回溯会少踩很多坑。7.1 在线评测环境与本地调试环境的分工LeetCode 提交的本质是你实现一个函数平台用多组测试数据调用它并把返回值与预期结果比较。本地调试时可以自由加print、画表格、测试小样例提交前要把函数返回值检查清楚不要在函数内部打印多余内容因为在线评测只关心返回值。建议在本地准备一个debug脚本目录把爬楼梯、背包、LIS、LCS 这类经典模板都跑一遍至少保证空输入能正常返回。长度为 1 的输入能正常返回。所有元素相等或降序的边界分布合法。每个示例输出的结果和题目示例一致。7.2 打印 DP 表的通用模板调试二维 DP 时通用的打印方式类似下面这样。填充 LCS 表时把每一步的内容打出来能直观看到转移方向def debug_lcs(text1: str, text2: str) - int: n, m len(text1), len(text2) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 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]) print( , [] list(text2)) for i in range(n 1): row_label if i 0 else text1[i - 1] print(row_label, dp[i]) return dp[n][m] print(debug_lcs(abcde, ace))一旦看到某一行突然没有增长或者某个对角线方向明显错误就能快速定位是初始化问题还是转移条件问题。7.3 动态规划常见 WA、TLE、RE 排查顺序现象常见原因检查顺序处理建议答案小 1、大 1 或只对示例成立初始化边界和递归边界不一致检查空输入、单元素输入、最小值输入用小样例手动填一遍 DP 表比对表头含义背包题答案偏大一维滚动数组内层正序物品被重复选检查容量循环是否从大到小改成range(capacity, w - 1, -1)子序列题返回dp[n-1]而不是max(dp)最终答案不在最后一个状态检查状态定义是否“以 i 结尾”循环内维护ans max(ans, dp[i])下标越界二维 DP 下标从 0 开始取nums[j-1]时搞混检查每个数组访问确认i-1和j-1对应关系使用偏移下标dp[i][j]对应text1[i-1]和text2[j-1]超时暴力递归没有记忆化或复杂度设计错误确认递归树是否重复计算先写记忆化再转迭代 DP递归栈溢出状态过多递归深度过深检查输入规模是否超过递归深度限制换成自底向上迭代 DP一个更实用的经验是LeetCode 动态规划题的输入规模通常会提示复杂度。n 在 1000 左右时O(n^2) 一般是可行方向n 到 10^5 时需要考虑贪心、二分优化或状态压缩。提交前先估算一下自己写的是不是能承受目标规模。7.4 下一步从三类模板扩展到更多背包变体把背包、LIS、LCS 三类题刷透之后后面很多新题会在它们的基础上改造完全背包每种物品可以选无限次一维滚动时内层循环改为正序对比 0-1 背包的倒序正好是反向理解。分组背包每组内最多选一个遍历顺序会变成“组外层、容量中层、组内元素内层”。多重背包、多维背包状态维度增加例如除了容量还限制数量或物品带类别。“分割等和子集”“目标和”等 LeetCode 题本质是“能否选满某个容量”需要把最大值问题转换成布尔判断问题。读题时先判断模型属于哪一类是基于“位置 i”的序列 DP基于“容量 j”的背包 DP还是基于“两个指针 i、j”的字符串二维 DP。判断出模型后再按“状态、决策、初始化、遍历顺序”四步走。练习时不要每道题都跳到代码先在草稿纸上写一句“最后一步有几个选择”再写状态定义。跑通一道题后专门复盘如果我把某个数组值改成负数、把严格递增改成非递减、把背包容量改成“恰好装满”状态和转移要怎么改。这种复盘比单纯追求 AC 数量更能训练建模能力。动态规划题的学习闭环可以总结成写递归确认子问题加缓存确认重复子问题改迭代确认填表顺序打印小