打家劫舍与买卖股票：状态机 DP

有一大类动规题，每一步都处于某个明确的"状态"（偷还是没偷、持有股票还是空仓），决策就是状态之间的跳转——这类题统称状态机 DP。本文用它串起两大家族：打家劫舍三连和股票系列，你会发现"升级版"无非是给状态机加维度。

一、打家劫舍 I：线性基础版（198）

相邻两间房不能同时偷，求能偷到的最大金额。对每间房只有两种决策，这就是最朴素的状态机：

状态	含义	来源
偷第 i 间	拿到 `nums[i]`，且上一间必没偷	`dp[i-2] + nums[i]`
不偷第 i 间	保住前 i-1 间的最大成果	`dp[i-1]`

把两个状态合并成一条递推式：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，初始化 dp[0]=nums[0]、dp[1]=max(nums[0], nums[1])：

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        // 不偷 i：沿用 dp[i-1]；偷 i：上一间必须跳过
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}

二、打家劫舍 II：环形拆解（213）

房间首尾相连成一个圈，首尾相邻也不能同偷。环没法直接做，但可以拆成两条链：

情形 A：偷第 0 间 → 第 n-1 间必不偷，等价于在 [0, n-2] 上做线性打家劫舍；
情形 B：不偷第 0 间 → 在 [1, n-1] 上做线性打家劫舍。

两种情形覆盖了所有可能（第 0 间偷或不偷，不存在第三种），取较大者即可：

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    // 拆两条链：去掉尾 / 去掉头，分别跑线性版本
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
 
// 在 [start, end] 上跑 198 的线性 dp
private int robRange(int[] nums, int start, int end) {
    if (start == end) return nums[start];
    int prev2 = nums[start];
    int prev1 = Math.max(nums[start], nums[start + 1]);
    for (int i = start + 2; i <= end; i++) {
        int cur = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

环形问题的通用套路：拆掉环上的一个约束点，化成若干条线性链取最值。

三、打家劫舍 III：树形 DP（337）

房子排成二叉树，直接相连的父子不能同偷。在树上做 DP，每个节点要返回两个状态，用后序遍历（先算子树，再决定自己）：

状态	含义	转移
`steal`	偷当前节点	`node.val + 左不偷 + 右不偷`（儿子只能不偷）
`skip`	不偷当前节点	`max(左偷,左不偷) + max(右偷,右不偷)`（儿子随便）

public int rob(TreeNode root) {
    int[] ans = dfs(root);
    return Math.max(ans[0], ans[1]);
}
 
// 返回 [偷该节点的最大收益, 不偷该节点的最大收益]
private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left = dfs(node.left);    // 先算左右子树
    int[] right = dfs(node.right);
    int steal = node.val + left[1] + right[1];            // 儿子必须不偷
    int skip = Math.max(left[0], left[1])
             + Math.max(right[0], right[1]);              // 儿子自由选择
    return new int[]{steal, skip};
}

为什么不能用单个 dp[node] 表示"以 node 为根的最大收益"？因为"爷爷和孙子能同时偷"这类信息只有把偷/不偷分开携带，父节点才能正确决策——树形 DP 常见形态就是每个节点返回一个状态数组。

四、股票系列：两状态起步

121. 只能交易一次

状态机只有两个状态，逐日跳转：

持有 hold[i]：今天手上有一股      不持有 sold[i]：今天手上没股票
  ↓ 买入(来自空仓)                 ↓ 卖出(来自持有)
hold[i] = max(hold[i-1], -prices[i])     ← 之前就持有，或今天买入
sold[i]  = max(sold[i-1], hold[i-1] + prices[i])   ← 一直没买，或今天卖出

public int maxProfit(int[] prices) {
    int hold = -prices[0], sold = 0;
    for (int i = 1; i < prices.length; i++) {
        hold = Math.max(hold, -prices[i]);              // 只能买一次，成本就是 -今日价
        sold = Math.max(sold, hold + prices[i]);
    }
    return sold;    // 最后一定是不持有更优（或相等）
}

122. 可以无限次交易

转移只改一处：买入的来源从"初始资金"变成"上一次卖出的累计收益"，即 hold = max(hold, sold - price)：

public int maxProfit(int[] prices) {
    int hold = -prices[0], sold = 0;
    for (int i = 1; i < prices.length; i++) {
        hold = Math.max(hold, sold - prices[i]);   // 卖了还能再买
        sold = Math.max(sold, hold + prices[i]);
    }
    return sold;
}

五、加维度：限定 k 次交易（123 / 188）

123 要求最多交易 2 次。交易次数也成了状态，把"第 j 次持有/不持有"展开成 2k+1 个状态（k=2 时共 5 个）：

状态转移表（k = 2）：
dp[0]        从不持有任何股票，恒为 0（作为买入成本的减法基准）
hold1[i] = max(hold1[i-1], dp[0] - prices[i])    ← 第 1 次持有
sold1[i] = max(sold1[i-1], hold1[i-1] + prices[i]) ← 完成第 1 次交易
hold2[i] = max(hold2[i-1], sold1[i-1] - prices[i]) ← 第 2 次持有，接在 sold1 之后
sold2[i] = max(sold2[i-1], hold2[i-1] + prices[i]) ← 完成第 2 次交易

public int maxProfit(int[] prices) {
    int hold1 = -prices[0], sold1 = 0;
    int hold2 = -prices[0], sold2 = 0;
    for (int i = 1; i < prices.length; i++) {
        hold1 = Math.max(hold1, -prices[i]);
        sold1 = Math.max(sold1, hold1 + prices[i]);
        hold2 = Math.max(hold2, sold1 - prices[i]);   // 第 2 次建立在第 1 次之上
        sold2 = Math.max(sold2, hold2 + prices[i]);
    }
    return sold2;
}

188 把 2 次推广到任意 k 次，用数组代替手写展开即可（k 超过 n/2 时退化为 122 的无限次版本，直接剪枝）：

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {                          // 交易次数够用，等价无限次
        int sold = 0, hold = -prices[0];
        for (int i = 1; i < n; i++) {
            hold = Math.max(hold, sold - prices[i]);
            sold = Math.max(sold, hold + prices[i]);
        }
        return sold;
    }
    int[] hold = new int[k + 1], sold = new int[k + 1];
    for (int j = 1; j <= k; j++) hold[j] = -prices[0];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            hold[j] = Math.max(hold[j], sold[j - 1] - prices[i]);
            sold[j] = Math.max(sold[j], hold[j] + prices[i]);
        }
    }
    return sold[k];
}

六、三状态：含冷冻期（309）

卖出后第二天不能买入，状态机多出一个"冷冻期"。注意建模方式不唯一，下面是一种清晰的三状态划分：

状态	含义	今天能从哪些状态来
持有 hold	手上有股	前一天持有，或前一天是"不持有且未冷冻"（今天买入）
冷冻 cool	今天刚卖出，明天冷冻	前一天持有（今天卖出）
空闲 free	不持有也不在冷冻	前一天空闲，或前一天冷冻

public int maxProfit(int[] prices) {
    int hold = -prices[0], cool = 0, free = 0;
    for (int i = 1; i < prices.length; i++) {
        int nHold = Math.max(hold, free - prices[i]);  // 继续持有 / 从空闲买入
        int nCool = hold + prices[i];                  // 今天卖出 → 明天冷冻
        int nFree = Math.max(free, cool);              // 冷冻结束 / 继续空闲
        hold = nHold; cool = nCool; free = nFree;
    }
    return Math.max(cool, free);
}

含手续费是 122 的小变形，卖出时多减一笔 fee 即可，不再展开。

七、复杂度与易错点

复杂度：打家劫舍 I/II 为 O(n)/O(1) 空间（II 用滚动变量）；树形 337 为 O(n) 每节点访问一次；股票系列均为 O(n)，k 次版本 O(n·k)。

易错点清单：

337 树形 DP 的 skip 状态要写 max(偷, 不偷) 而不是只取"不偷"——不偷自己时儿子偷不偷都要比。
213 拆链时下标边界：一条是 [0, n-2]，另一条是 [1, n-1]，n=1 要单独返回。
121 与 122 只差买入来源（-price vs sold - price），抄错公式答案就翻倍或归零。
188 忘记 k >= n/2 的剪枝，数组开得过大；或初始化 hold[j] 时漏了第一天价格。
309 的返回值要取 max(cool, free)，只返回 free 会漏掉"最后一天刚卖出"的情形。

八、LeetCode 题目清单

题号	题名	一句话考点
198	打家劫舍	相邻约束的线性两决策递推
213	打家劫舍 II	环形拆两条链取最大
337	打家劫舍 III	树形 DP，节点返回偷/不偷双状态
121	买卖股票的最佳时机	两状态机，只能一次交易
122	买卖股票的最佳时机 II	买入来源改为累计收益
123	买卖股票的最佳时机 III	2 次交易的五状态展开
188	买卖股票的最佳时机 IV	推广到 k 次，k≥n/2 剪枝
309	最佳买卖股票时机含冷冻期	三状态：持有/冷冻/空闲
714	买卖股票的最佳时机含手续费	122 变形，卖出减 fee

参考

代码随想录 · 打家劫舍与股票系列