如果你按顺序刷过《代码随想录》前面的背包章节很可能会有一个错觉动态规划不过就是“选还是不放”的二维表格推一推稍微优化一下滚动数组就完事了。但当你翻到动态规划下这章遇到打家劫舍、股票问题、子序列问题的时候画风突然就变了——打家劫舍的递推开始“隔一个跳一个”股票的 DP 数组要维护“持有/不持有”两个状态子序列则动不动就开一个二维 dp 表还要小心翼翼地处理空串边界。这一章的跨度确实比背包大很多但同时也是动态规划从“背模板”走向“自己设计状态”的分水岭。这篇博文就是针对《代码随想录》第 11 章这三个题型做一次完整的拆解我会把打家劫舍、股票问题、子序列问题各自的递推思路、初始化陷阱、Python3 实现细节全部讲透。内容不要求你提前会背包只需要你至少做过几道简单的 DP 题能看懂一维 dp 数组和二维 dp 数组的基本含义就够。文章里所有的代码都用 Python3 写方便实验和调试也能让你把注意力完全放在状态转移上而不是被语法细节绊住。1. 这章的跨度为什么比背包大从“选与不选”到“持有与不持有”1.1 背包问题给我们的思维定势背包问题的本质是“对每个物品做一次二选一决策”放进去还是不放。这个决策直接影响的是背包容量所以我们习惯用dp[i][j]表示“前 i 个物品装进容量 j 的背包能获得的最大价值”或者压缩成dp[j]一维滚动数组。不管怎么变状态里始终有一个“背包容量”作为坐标轴物品的顺序性其实不强。但到了打家劫舍你会发现一个尴尬的事实你没法用“容量”这种物理量的维度来定义状态了。这个问题没有容量限制只有“相邻两个房子不能同时偷”的约束所以能用的维度变成了“偷到第几间房”以及“当前这间房偷还是不偷”。这就逼着你把“决策本身”作为状态的一部分而不是把决策当作一个转移动作。1.2 持有与不持有股票题里真正的维度到了股票问题这个感觉会更强烈。你不再是在“物品”和“容量”之间做选择而是在“时间”和“持仓状态”之间做选择。每一天有两个状态持有股票、不持有股票。持有和不持有的转移其实就是“买入”和“卖出”这两个动作的结果。这种状态设计在背包里从来没出现过。背包中的“选”和“不选”是直接产生价值的而股票里的“持有”本身不产生价值只有买和卖的价差才产生利润。所以你不能只靠dp[i] max(dp[i-1], ...)这种一维套路而必须引入“状态维”一般是dp[i][0]表示第 i 天结束时不持有股票的最大现金dp[i][1]表示第 i 天结束时持有股票的最大现金。1.3 子序列问题二维 dp 是躲不开的子序列问题则引入了另一层复杂度两个序列互相比较或者一个序列内部做最长递增。最长递增子序列LIS好歹还是一维dp[i]但最长公共子序列LCS一上来就是dp[i][j]表示“text1 的前 i 个字符”和“text2 的前 j 个字符”的最长公共子序列长度。这就会遇到背包很少遇到的两个坑第一个坑是初始化二维表的第 0 行和第 0 列通常表示空串初始值必须设为 0第二个坑是遍历时要注意字符串索引从 1 开始避免i-1越界。很多人第一次写 LCS都会在dp[i][j] dp[i-1][j-1] 1的地方把i-1写错成idebug 半小时也看不出问题。所以我的建议是在开始刷这三类题之前先在心里把“状态维度”这件事想明白。背包帮我们练熟的是“二维表格 滚动数组”但这章帮我们练的是“状态设计能力”——你知道状态应该包含哪些信息才知道递推公式该怎么写。这也是为什么同样的 DP有人一看题就能写转移方程有人只能默写模板差别就在这。2. 打家劫舍三连状态是路过的房子决策是偷还是不偷2.1 第 198 题从最朴素的递推开始打家劫舍 LeetCode 198 是这章的第一题题目本身很简单每间房有现金相邻两间不能同时偷。我最早做这题的时候第一反应是维护一个“偷到第 i 间房时能拿到的最大金额”表达式是dp[i] max(dp[i-1], dp[i-2] nums[i])这个转移要解释清楚当你站在第 i 间房前面只有两个选择。要么不偷这一间结果就是dp[i-1]跟偷到上一间时一样。要么偷这一间代价是上一间不能偷所以是dp[i-2] nums[i]。这两者取最大值就是到第 i 间为止的最佳收益。这个转移看起来简单但它有一个关键地方dp[i-1]本身不一定是“偷了第 i-1 间”的结果它只是“处理完前 i-1 间房能拿到的最大值”。所以max(dp[i-1], dp[i-2] nums[i])的写法实际上已经隐含地处理了“跳过一间”的可能性不需要再去判断 i-1 那间到底偷没偷。用 Python3 实现时我喜欢直接做滚动数组因为每间房只需要前两个状态class Solution: def rob(self, nums: List[int]) - int: prev2, prev1 0, 0 for num in nums: cur max(prev1, prev2 num) prev2, prev1 prev1, cur return prev1这里prev2相当于dp[i-2]prev1相当于dp[i-1]。如果你第一次接触滚动数组建议先写出完整的一维数组版本再压缩成这种形式不然直接看滚动版本容易发懵。2.2 第 213 题环形数组怎么拆成线性问题第 213 题把数组改成环形第一间房和最后一间房也算相邻。这时如果你还是用同一个 DP 从头扫到尾就会出现“首尾同时被偷”的非法解。正确的思路是拆成两个线性问题求最大值不偷第一间只考虑[1, n-1]区间。不偷最后一间只考虑[0, n-2]区间。然后把两个结果取最大值。为什么这样是对的因为环形带来的唯一额外约束就是“首尾不能同时偷”所以要么首不偷要么尾不偷只要分别把这两条路堵死剩下的区间又变回线性了。这个“拆区间”的技巧在环形 DP 里非常常见不只是打家劫舍环形数组求最大子数组和也会用到。我实现的 rob_range 函数和主函数分离代码看起来更清晰class Solution: def rob(self, nums: List[int]) - int: n len(nums) if n 1: return nums[0] def rob_range(start: int, end: int) - int: prev2, prev1 0, 0 for i in range(start, end 1): cur max(prev1, prev2 nums[i]) prev2, prev1 prev1, cur return prev1 return max(rob_range(0, n - 2), rob_range(1, n - 1))这里要注意区间是左闭右闭所以end要传到n-2或n-1别把最后一个元素搞丢了。2.3 第 337 题二叉树上的打家劫舍最考验递归状态第 337 题把线性数组换成了完全二叉树。每个节点有值直接相连的父子节点不能同时取。这题如果做法不对最容易写出的错误代码是递归调用rob(node.left)和rob(node.right)同时在递归过程中重复计算子问题导致指数级复杂度。正确姿势是后序遍历每个节点返回一个长度为 2 的列表[不偷当前节点的最大收益, 偷当前节点的最大收益]。关键转移如果偷当前节点左右孩子都不能偷所以收益是node.val left[0] right[0]。如果不偷当前节点左右孩子各自取最大值收益是max(left) max(right)。Python3 写起来非常简洁class Solution: def rob(self, root: Optional[TreeNode]) - int: def dfs(node): if not node: return [0, 0] left dfs(node.left) right dfs(node.right) not_rob max(left) max(right) rob node.val left[0] right[0] return [not_rob, rob] return max(dfs(root))这个递归返回二元组的设计比全局变量或者记忆化搜索都要自然。因为它把“状态”嵌入了递归返回值让每个节点只需要关心自己孩子返回的信息不用去管整棵树的额外状态。本质上这就是树形 DP只是用递归隐式地完成了遍历顺序。我当时从第 198 题做到第 337 题最大的感受是打家劫舍系列真正的考点不是“递推公式有多难”而是你能不能根据数据结构的变化调整状态的组织方式。数组是一维滚动环形数组是拆区间二叉树是递归返回二元状态。数据结构一变状态定义就要跟着变。3. 股票问题六连一套持有与不持有的状态机跑完全部变体3.1 从一次买卖到无限次买卖状态机雏形股票问题的 LeetCode 系列一共有六道题121一次买卖、122无限次买卖、123最多两笔、188最多 k 笔、309含冷冻期、714含手续费。表面上看题号很多实际上它们共享同一个状态框架每天只关心“手上有没有股票”。我先拿 122 无限次买卖来讲这个框架。定义两个状态hold表示当天结束时手里持有股票的最大现金。cash表示当天结束时手里没有股票的最大现金。每天可以做的操作是买入或卖出。买入会让cash变成hold卖出会让hold变成cash。所以转移可以写成class Solution: def maxProfit(self, prices: List[int]) - int: hold -prices[0] cash 0 for p in prices[1:]: new_hold max(hold, cash - p) new_cash max(cash, hold p) hold, cash new_hold, new_cash return cash我特意用new_hold和new_cash两个临时变量是因为如果直接写成hold max(hold, cash - p)再cash max(cash, hold p)后面这行的hold已经是更新过的值就会把“今天先买后卖”这种等价于没操作的情况也搅和进去。虽然最终结果大概率一样但初学者很难一眼看出为什么一样不如用旧状态同步更新新状态逻辑无歧义。这里要注意买入时cash - p用的是“当前不持有状态下的现金”所以无限次买卖能反复赚钱的原因就在这每次买入的现金基数里已经包含了之前交易累积的利润。3.2 最多两笔和最多 k 笔把状态量化123 题要求最多完成两笔交易。直接把两个状态扩展成五个状态0表示什么都没做1表示第一次持有2表示第一次卖出后不持有3表示第二次持有4表示第二次卖出后不持有。状态转移就是依次在奇数位买入、偶数位卖出class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) if n 0: return 0 dp [[0] * 5 for _ in range(n)] dp[0][1] -prices[0] dp[0][3] -prices[0] for i in range(1, n): dp[i][1] max(dp[i-1][1], -prices[i]) dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i]) dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i]) dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i]) return max(dp[-1])为什么要设置两次初始的-prices[0]因为第 0 天可以“第一次买入”也可以“先买再卖再买”虽然这不现实但由于同一天买卖利润为 0所以把dp[0][3]初始化成-prices[0]是为了让第二次买入有机会在第 0 天发生后续转移才能自洽。188 题把“最多两笔”推广成“最多 k 笔”时不需要重新想转移逻辑只要把状态扩展到2*k1个奇数位持有偶数位不持有。奇数位从上一个不持有状态买入偶数位从上一个持有状态卖出。class Solution: def maxProfit(self, k: int, prices: List[int]) - int: n len(prices) if n 0 or k 0: return 0 dp [0] * (2 * k 1) for j in range(1, 2 * k 1, 2): dp[j] -prices[0] for p in prices[1:]: for j in range(1, 2 * k 1): if j % 2 1: dp[j] max(dp[j], dp[j-1] - p) else: dp[j] max(dp[j], dp[j-1] p) return dp[2 * k]这里我故意用一维滚动数组因为只要理解了“奇数买入、偶数卖出”的规律j 从 1 到 2k 的顺序更新实际上不会造成状态污染——即便有“今天买今天卖”的中间态混入它的利润也是 0不会让最大值变大。不过如果你对这种写法没有把握完全可以直接写二维数组版本牺牲一点空间换安心。3.3 冷冻期和手续费状态机规则的微调309 题加了“卖出后的第二天不能买入”的冷冻期。如果还沿用两个状态你会发现“不持有”内部其实有两种子情况一种是刚卖出进入冷冻期另一种是冷冻期已经结束可以正常买入。所以更清晰的方案是三个状态hold持有股票。free不持有且不在冷冻期。cool不持有且刚卖出处于冷冻期。转移关系是从free可以买入变成hold。从hold可以卖出变成cool。从cool在第二天会自然回到free。从free可以继续保持free。Python3 代码class Solution: def maxProfit(self, prices: List[int]) - int: n len(prices) if n 0: return 0 hold -prices[0] free 0 cool 0 for p in prices[1:]: new_hold max(hold, free - p) new_free max(free, cool) new_cool hold p hold, free, cool new_hold, new_free, new_cool return max(free, cool)714 题加手续费就更简单了在 122 的基础上卖出时扣掉手续费即可。只改一行new_cash max(cash, hold p - fee)。到这里你会发现股票问题看似六道其实核心就是一个状态机不同的题只是在状态数量或者转移边上做了加减法。只要你能画出“持有/不持有”的状态转移图代码就是按图索骥的事情。4. 子序列题型的真相连续与不连续是两套 DP 逻辑4.1 最长递增子序列一维 DP 的经典起点子序列问题里最长递增子序列LeetCode 300算是最有代表性的一道。它不要求子序列在原数组中连续只要求值严格递增。这类“不连续”问题的 DP 定义通常是dp[i]表示以nums[i]结尾的最长递增子序列长度。转移时对于每个i遍历它前面所有的j如果nums[j] nums[i]那么就可以把nums[i]接到nums[j]结尾的子序列后面得到dp[j] 1class Solution: def lengthOfLIS(self, nums: List[int]) - int: 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)这段代码最需要注意的是dp数组初始化为全 1因为任何单独一个元素本身就是长度为 1 的递增子序列。如果你把它初始化成全 0就会出现递归结果整体少 1 的经典错误。如果数组长度到几千甚至几万O(n^2) 会超时可以优化成贪心加二分。核心是维护一个tails数组tails[k]表示长度为 k1 的递增子序列中末位元素的最小值。遍历每个数用二分查找找到它应该放的位置。Python 的bisect模块帮我们封装好了import bisect class Solution: def lengthOfLIS(self, nums: List[int]) - int: 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)这个优化的正确性不是那么好理解你可以把它想象成“尽量让子序列的末尾元素更小从而给后续元素留更多扩展空间”。二分版本只能返回最长长度不能直接还原具体子序列但对绝大多数题目已经够用了。4.2 最长公共子序列二维表的初始化与索引偏移最长公共子序列LeetCode 1143是子序列系列里最需要谨慎处理的题。它要求在两个字符串中找到一个相同子序列且不要求字符在原串中连续。定义dp[i][j]为text1[:i]和text2[:j]的最长公共子序列长度。当text1[i-1] text2[j-1]时当前字符可以配对所以dp[i][j] dp[i-1][j-1] 1。当不相等时只能继承上方或左方中的较大值dp[i][j] max(dp[i-1][j], dp[i][j-1])。class Solution: def longestCommonSubsequence(self, text1: str, text2: str) - int: 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]为什么要让 i 和 j 从 1 开始遍历因为第 0 行和第 0 列代表“其中一个字符串为空”空串和任何字符串的公共子序列长度都是 0这是天然正确的初始化。于是遍历时比较的是text1[i-1]和text2[j-1]而不是text1[i]和text2[j]。很多初写者在这里懵住其实就是索引偏移没绕过来。4.3 连续型子数组和编辑距离由“断”与“不断”决定转移与“不连续”相对的是“连续”比如最长重复子数组LeetCode 718它要求两个数组里相同的部分是连续的。这时 DP 定义就不是“前缀的最优值”了而是dp[i][j]表示“以nums1[i-1]结尾”和“以nums2[j-1]结尾”这两个位置作为末尾的最长公共子数组长度。如果当前位置不相等前面再怎么连续都没用所以只能继承 0相当于断开class Solution: def findLength(self, nums1: List[int], nums2: List[int]) - int: m, n len(nums1), len(nums2) dp [[0] * (n 1) for _ in range(m 1)] ans 0 for i in range(1, m 1): for j in range(1, n 1): if nums1[i-1] nums2[j-1]: dp[i][j] dp[i-1][j-1] 1 ans max(ans, dp[i][j]) # 不相等时 dp[i][j] 保持 0 return ans对比 718 和 1143 你会发现一个核心差异1143 在不相等时做max(dp[i-1][j], dp[i][j-1])这样后面的字符还能借力前面已经算出的匹配结果718 在不相等时什么都不用做因为“连续”这个要求让任何中断都意味着重新计数。这个差异表面上只是有没有 else 分支实际上是两类问题的本质区别不连续问题走“可继承”的转移连续问题走“容易清零”的转移。编辑距离LeetCode 72其实和最长公共子序列长得非常像同样都是二维前缀比较。只是编辑距离的转移对应三种操作删除、插入、替换。删除对应dp[i-1][j]插入对应dp[i][j-1]替换对应dp[i-1][j-1]。当两个字符相等时不需要替换所以直接继承dp[i-1][j-1]不相等时三种操作取最小再加 1class Solution: def minDistance(self, word1: str, word2: str) - int: m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]编辑距离的初始化必须把第 0 行和第 0 列分别填成行号或列号因为把一个字符串变成空串需要删掉所有字符。这里和 LCS 的初始化不同LCS 空串天然是 0编辑距离空串却代表“删除成本”所以不能照搬。5. 三类题串完之后的复盘初始化、遍历顺序、状态定义一个都不能少5.1 状态定义失之毫厘递推公式谬以千里把打家劫舍、股票问题、子序列问题放在一起看你会得到一个很重要的结论递推公式永远服务于状态定义。打家劫舍的状态是“偷到第 i 间为止的最大收益”所以转移用max(dp[i-1], dp[i-2] nums[i])股票的状态是“第 i 天持有或不持有”所以转移是max(保持原状态, 从另一个状态买入/卖出)子序列的状态是“以某个位置结尾的子序列长度”或“两个前缀的最优匹配”所以转移要么是“能不能接在后面”要么是“继承还是配对”。如果你拿到一道题发现递推公式写不出来八成不是数学不好而是状态定义没想清楚。反过来状态定义一旦到位递推公式往往就是一句“如果用当前字符匹配取什么如果不匹配取什么”的话。5.2 初始化是 DP 最容易翻车的地方我刷完这一章后统计了一下自己踩过的坑初始化相关的占了将近一半。打家劫舍 198 要初始化prev2 0, prev1 0让第一间房能正确计算出nums[0]打家劫舍 337 的空节点要返回[0, 0]保证递归能终止股票 123 要把dp[0][1]和dp[0][3]都设成-prices[0]LIS 要把 dp 全初始化为 1LCS 要保留第 0 行第 0 列的全 0编辑距离要把第 0 行第 0 列填成 i 和 j。每一次错误都是因为“初始状态没有表达清楚空串/空集合/第 0 天的语义”。我的建议是每写一道 DP 题先问自己三个问题。第一个问题空输入或者第 0 个元素的状态应该是什么第二个问题如果某一维长度为 0表格里应该填什么第三个问题初始化完成后遍历的第一个位置是否已经能正确利用这些初始值这三个问题全过一遍初始化基本不会出错。5.3 遍历顺序的直觉从小的子问题到大的子问题遍历顺序看起来是代码里的表面功夫实际上决定 DP 正确性。打家劫舍从前往后扫是因为每间房只依赖前面的房间股票问题从第 1 天遍历到第 n 天是因为每天只依赖前一天的状态LCS 和编辑距离的双重循环一定要让 i 和 j 从小到大因为dp[i][j]依赖的dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]都必须先被计算出来。如果你发现输出不对优先检查遍历顺序。一个常见的隐性错误是在二维 DP 里如果你让 i 从小到大但 j 从大到小就可能出现依赖项尚未计算的情况尤其是滚动数组版本的 LCS更容易被这种顺序坑到。5.4 用 Python3 刷这几类题的具体优势最后聊一下为什么我坚持用 Python3 来刷这章。严格来说这些题用什么语言都能做但 Python3 有几个实际好处。第一代码量少状态转移的语义可以直接映射成两三行表达式不会出现写了大几十行还在处理指针边界的情况。第二bisect、functools.lru_cache、itertools这些标准库对算法题的支撑非常够用比如 LIS 的二分优化直接调bisect_left就行。第三列表推导式用来初始化二维表很顺手[[0] * (n 1) for _ in range(m 1)]一行就能建好 LCS 的 DP 表。但注意一个 Python 的常见陷阱如果要初始化一个二维数组不要写[[0] * (n1)] * (m1)这样生成的是同一个内部列表的引用改一行会连带改所有行。老老实实用列表推导式或者每行新建一个列表。5.5 这章的题目安排为什么是“打家劫舍、股票、子序列”的顺序刷完整章我一直在想一个问题为什么《代码随想录》要把这三类题放在一起我的理解是它们对应的能力阶梯刚好递进。打家劫舍训练你在一维场景下把“决策”纳入状态股票问题训练你在有多个操作动作时设计更细的状态机子序列问题训练你在二维场景下通过表结构维护最优子结构。每一类题都不是孤立的知识点而是对“状态设计”这个能力的反复强化。等你把三类题都做熟再回头看背包问题你会发现自己已经能够从状态设计的角度去理解背包的dp[i][j]了而不是背下那个两重循环就完了。我自己常用的复习办法是手动整理一张表列出每道题的状态定义、递推公式、初始化、遍历顺序四个要素。写下来的过程比光看题解有用得多因为整理时你会被迫关注那些凑合看题能混过去、但自己动手就会出错的细节。我建议你也试试这个办法刷完一章就做这样一张表要不了多久动态规划的正确率会明显往上走。