如果你按顺序刷过《代码随想录》前面的背包章节，很可能会有一个错觉：动态规划不过就是“选还是不放”的二维表格推一推，稍微优化一下滚动数组就完事了。但当你翻到动态规划（下）这章，遇到打家劫舍、股票问题、子序列问题的时候，画风突然就变了——打家劫舍的递推开始“隔一个跳一个”，股票的 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写错成i，debug 半小时也看不出问题。
所以我的建议是：在开始刷这三类题之前，先在心里把“状态维度”这件事想明白。背包帮我们练熟的是“二维表格 + 滚动数组”，但这章帮我们练的是“状态设计能力”——你知道状态应该包含哪些信息，才知道递推公式该怎么写。这也是为什么同样的 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*k+1个：奇数位持有，偶数位不持有。奇数位从上一个不持有状态买入，偶数位从上一个持有状态卖出。
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] + 1：
class 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]表示长度为 k+1 的递增子序列中末位元素的最小值。遍历每个数，用二分查找找到它应该放的位置。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]；不相等时，三种操作取最小再加 1：
class 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 全初始化为 1；LCS 要保留第 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] * (n+1)] * (m+1)，这样生成的是同一个内部列表的引用，改一行会连带改所有行。老老实实用列表推导式，或者每行新建一个列表。
5.5 这章的题目安排为什么是“打家劫舍、股票、子序列”的顺序
刷完整章，我一直在想一个问题：为什么《代码随想录》要把这三类题放在一起？
我的理解是，它们对应的能力阶梯刚好递进。打家劫舍训练你在一维场景下把“决策”纳入状态；股票问题训练你在有多个操作动作时设计更细的状态机；子序列问题训练你在二维场景下通过表结构维护最优子结构。每一类题都不是孤立的知识点，而是对“状态设计”这个能力的反复强化。等你把三类题都做熟，再回头看背包问题，你会发现自己已经能够从状态设计的角度去理解背包的dp[i][j]了，而不是背下那个两重循环就完了。
我自己常用的复习办法是：手动整理一张表，列出每道题的状态定义、递推公式、初始化、遍历顺序四个要素。写下来的过程比光看题解有用得多，因为整理时你会被迫关注那些凑合看题能混过去、但自己动手就会出错的细节。我建议你也试试这个办法，刷完一章就做这样一张表，要不了多久，动态规划的正确率会明显往上走。
