打家劫舍系列——线性DP到树形DP的完整演进

适读人群：Java后端工程师、DP进阶学习者 | 阅读时长：约22分钟 | 难度：Medium

---

开篇故事

打家劫舍这道题，我第一次做是在字节跳动的二面。那是下午三点，面试官让我在白板上写。我以为是简单题，刷刷写完了基本的线性DP。面试官抬起头说："好，现在把房子排成一个圈，首尾相连，怎么办？"

我改了改，处理了环形的情况。他又说："现在房子不是线性排列，而是一棵树，每个节点是一个房子，父节点和子节点之间有报警，怎么办？"

我当时脑子瞬间短路。树形DP在当时对我来说几乎是盲区。白板上划了好几道草稿，总算写了个大致正确的方向，但细节上有漏洞。

这道题让我意识到，DP的进化路径是有规律的：线性 → 环形 → 树形。每一步都是对约束条件的延伸，解法框架也随之演变。把这三道题放在一起吃透，你对DP的理解会上一个台阶。

今天就来彻底拆解打家劫舍系列，从198到213再到337，一步一步看清楚每次约束变化背后的解法演进。

---

一、题目解析

LeetCode 198. 打家劫舍

描述：一排房屋，每个房屋有一定数量的金钱，相邻的房屋如果都被偷则触发报警。求不触发报警的情况下，能偷到的最大金额。

示例：

• 输入：[1,2,3,1]，输出：4（偷第1和第3个）
• 输入：[2,7,9,3,1]，输出：12（偷第1、第3、第5个）

约束：1 ≤ nums.length ≤ 100，0 ≤ nums[i] ≤ 400

LeetCode 213. 打家劫舍II

描述：在198的基础上，房屋围成一个圆圈，第一个和最后一个房屋相邻。

示例：

• 输入：[2,3,2]，输出：3（不能同时偷第1和第3个）
• 输入：[1,2,3,1]，输出：4

LeetCode 337. 打家劫舍III

描述：小偷发现了一个特殊的地方，房屋排列成二叉树结构，直接相连的两个房屋如果都被偷则触发报警。

示例：输入树根为3，左子树2（右孩子3），右子树3（右孩子1），输出：7（偷根节点3、左孩子的右孩子3、右孩子的右孩子1）

三道题的约束对比：

题号	结构	约束	难度
198	线性数组	相邻不能同时选	Easy/Medium
213	环形数组	相邻不能同时选 + 首尾也相邻	Medium
337	二叉树	父子节点不能同时选	Medium

---

二、198——线性DP基础

2.1 状态定义

这道题的关键约束是"相邻不能同时选"。

我用"最后一步分析法"来推导状态：

站在第 i 个房屋，有两种选择：

1. 偷第 i 个：那么第 i-1 个一定不能偷，能偷到的最多钱 = 偷到第 i-2 个时的最多钱 + nums[i]
2. 不偷第 i 个：能偷到的最多钱 = 偷到第 i-1 个时的最多钱（第i-1个偷不偷都行，取最大值）

定义 dp[i] = 考虑前 i 个房屋（索引0到i-1）能偷到的最大金额

注意这里"考虑前i个"并不要求第i个一定要偷，只是考虑范围截止到第i个。

2.2 状态转移方程

dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

其中 nums[i-1] 是第i个房屋的金额（0-indexed数组中的第i-1个元素）。

含义解读：

• dp[i-1]：不偷第i个房屋，最大收益就是前i-1个房屋的最大收益
• dp[i-2] + nums[i-1]：偷第i个房屋，那么第i-1个不能偷，收益是前i-2个的最大收益加上第i个的金额

2.3 边界条件

• dp[0] = 0：没有房屋，收益为0
• dp[1] = nums[0]：只有一个房屋，直接偷走

状态转移示意

nums = [2, 7, 9, 3, 1]

| i  | dp[i]                          | 解释               |
|----|--------------------------------|--------------------|
| 0  | 0                              | 无房屋             |
| 1  | 2 = nums[0]                    | 只偷第1个           |
| 2  | max(2, 0+7)=7                  | 不偷1偷2，或只偷1   |
| 3  | max(7, 2+9)=11                 | 偷1偷3             |
| 4  | max(11, 7+3)=11                | 偷1偷2不能，取11    |
| 5  | max(11, 11+1)=12               | 偷1偷3偷5          |

public class HouseRobber {
    
    /**
     * 198. 打家劫舍 - 基础线性DP
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)，可优化到O(1)
     */
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        // dp[i] = 考虑前i个房屋能偷的最大金额
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        
        for (int i = 2; i <= n; i++) {
            // 不偷第i个：dp[i-1]
            // 偷第i个：dp[i-2] + nums[i-1]
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        
        return dp[n];
    }
    
    /**
     * 198. 空间优化版 O(1)
     */
    public int robOptimized(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        int prev2 = 0;          // dp[i-2]
        int prev1 = nums[0];    // dp[i-1]
        
        for (int i = 2; i <= n; i++) {
            int curr = Math.max(prev1, prev2 + nums[i - 1]);
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

---

三、213——环形DP：破环成链

3.1 环形的难点

环形比线性难在哪？就一点：第一个和最后一个房屋相邻，不能同时偷。

如果我们直接套线性DP，可能会选择同时偷第0个和第n-1个，这就违反了环形约束。

3.2 关键思路：破环成链

处理环形DP最经典的技巧叫"破环成链"：

如果第一个和最后一个不能同时选，那么分两种情况讨论：

1. 不包含最后一个房屋：对 nums[0...n-2] 做线性DP
2. 不包含第一个房屋：对 nums[1...n-1] 做线性DP

两种情况取最大值。

正确性证明：最优解中，要么不包含nums[0]，要么不包含nums[n-1]（或者两者都不包含）。情况1覆盖了"不含最后一个"的所有情况，情况2覆盖了"不含第一个"的所有情况，合并后覆盖了所有合法情况。

/**
 * 213. 打家劫舍II - 环形，破环成链
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
public int rob213(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    if (n == 2) return Math.max(nums[0], nums[1]);
    
    // 情况1：不偷最后一个，对[0, n-2]做线性DP
    int result1 = robRange(nums, 0, n - 2);
    // 情况2：不偷第一个，对[1, n-1]做线性DP
    int result2 = robRange(nums, 1, n - 1);
    
    return Math.max(result1, result2);
}

/**
 * 对nums[start, end]范围做线性打家劫舍
 */
private int robRange(int[] nums, int start, int end) {
    int prev2 = 0;
    int prev1 = nums[start];
    
    for (int i = start + 1; i <= end; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

破环成链的状态分析图：

---

四、337——树形DP：后序遍历携状态

4.1 树形DP的核心思想

树形DP是我觉得DP里最优雅的一类。它把DP和DFS结合在一起，在后序遍历（先处理孩子，再处理父节点）的过程中，自底向上地计算子问题的解。

对于打家劫舍III，每个节点有两种状态：

• 偷这个节点：两个子节点都不能偷
• 不偷这个节点：两个子节点可以偷也可以不偷，取各自的最大值

4.2 状态定义

定义 rob(node) 返回一个长度为2的数组 [notRob, rob]：

• notRob = rob(node)[0]：以node为根的子树，不偷node时的最大收益
• rob = rob(node)[1]：以node为根的子树，偷node时的最大收益

4.3 状态转移方程

设 left = dfs(node.left)，right = dfs(node.right)：

不偷node时：左右子节点可以随意选择（偷或不偷，各取最大）

notRob = max(left[0], left[1]) + max(right[0], right[1])

偷node时：左右子节点都不能偷

rob = node.val + left[0] + right[0]

最终答案为 max(dfs(root)[0], dfs(root)[1])。

4.4 为什么要返回两个值

这是树形DP区别于线性DP的关键设计。在线性DP中，dp[i]是一个值，因为"偷不偷第i个"这个决定已经被最大值合并了。

但在树形结构中，父节点的决策直接影响子节点的选择空间。如果我们只返回子树的最大值，父节点就无法知道这个最大值是"偷了子节点"还是"没偷子节点"得来的，也就无法正确计算父节点偷时的收益。

所以必须把"偷"和"不偷"分开返回，让父节点自己决策。

/**
 * 337. 打家劫舍III - 树形DP
 * 时间复杂度：O(n)，每个节点访问一次
 * 空间复杂度：O(h)，h为树的高度（递归栈）
 */
public class HouseRobberIII {
    
    public int rob(TreeNode root) {
        int[] result = dfs(root);
        // 返回偷根节点和不偷根节点的较大值
        return Math.max(result[0], result[1]);
    }
    
    /**
     * 后序DFS，返回 [不偷当前节点的最大收益, 偷当前节点的最大收益]
     */
    private int[] dfs(TreeNode node) {
        // 空节点：偷不偷都是0
        if (node == null) return new int[]{0, 0};
        
        // 递归处理左右子树（后序：先孩子再父节点）
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        
        // 不偷当前节点：左右子节点可以随意选择，各取最大
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        // 偷当前节点：左右子节点都不能偷（取left[0]和right[0]）
        int rob = node.val + left[0] + right[0];
        
        return new int[]{notRob, rob};
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

状态转移的树形图示（以示例为例）：

        3
       / \
      2   3
       \   \
        3   1

dfs(叶节点3左孩子) = [0, 3]
dfs(叶节点3右孩子) = [0, 1]
dfs(节点2):
  not_rob = max(0,0) + max(0,3) = 3   // 不偷2，可以偷2的右孩子3
  rob = 2 + 0 + 0 = 2                 // 偷2，孩子都不能偷
  return [3, 2]
dfs(节点3右):
  not_rob = max(0,0) + max(0,1) = 1
  rob = 3 + 0 + 0 = 3
  return [1, 3]
dfs(根节点3):
  not_rob = max(3,2) + max(1,3) = 3 + 3 = 6
  rob = 3 + 3 + 1 = 7
  return [6, 7]
答案 = max(6, 7) = 7

---

五、三道题的横向对比

特征	198线性	213环形	337树形
数据结构	数组	数组（环）	二叉树
关键技巧	线性DP	破环成链	后序DFS+双值返回
遍历方向	左到右	两次线性	后序（自底向上）
dp状态	一维	一维	每节点二值

---

六、举一反三

延伸题目：

1. LeetCode 740. 删除并获得点数：选了某个数就必须删除所有相邻值的数，本质上转化成打家劫舍
2. LeetCode 2560. 打家劫舍IV（Hard）：二分答案+DP，难度大升
3. 通用树形DP：选课问题（有依赖的背包）、树的最大独立集，都是337的延伸

树形DP通用框架：

1. 定义每个节点的状态（通常是数组或多个值）
2. 写后序DFS（先递归子节点，再计算当前节点）
3. 状态转移：当前节点的状态 = f(子节点状态)
4. 从根节点DFS，取最终状态的最优值

---

七、踩坑实录

坑一：213直接套线性DP

最常见的错误，直接把198的代码用在213上，完全不处理环形约束。偷了nums[0]又偷了nums[n-1]，触发报警。记住环形DP的通用处理方式就是"破环成链"，分两种情况取最大值。

坑二：337返回值顺序写反

dfs 返回 [notRob, rob] 还是 [rob, notRob]？这个顺序没有对错，但一定要和后续代码保持一致。我建议固定用 [0]表示不偷，[1]表示偷，并在代码里写上注释，不然写到一半就乱了。

坑三：337用HashMap缓存没必要

网上有些解法在337里用 HashMap 做记忆化缓存，其实完全没必要。因为我们是在后序DFS中自底向上计算，每个节点只访问一次，根本没有重复计算。HashMap 反而增加了空间开销。

坑四：198的dp数组下标偏移

我定义的是 dp[i] 表示前i个房屋，所以 dp[i] 对应 nums[i-1]，下标差了1。有些人喜欢 dp[i] 对应 nums[i]，这样边界初始化不一样。两种都对，但一定要在代码里统一，不要混用。

坑五：337递归没有null处理

树形DP的null处理是基础中的基础，但压力大的时候真的会忘。一定要在 dfs 的第一行处理 node == null 的情况，返回 {0, 0}。

---

八、总结

打家劫舍三部曲是学习DP演进路径的绝佳教材。从简单的线性约束，到环形约束的破环成链，再到树形结构的后序DFS携状态，每一步都有清晰的思路演变。

三条核心原则：

1. 线性DP：状态定义清晰，转移方向明确（前→后），滚动变量压缩空间
2. 环形DP：拆成两个子问题（分别去掉首或尾），取最大值
3. 树形DP：后序遍历，每个节点返回多状态，父节点自行合并决策

把这三道题吃透，遇到类似约束的DP题，脑子里就会有现成的思路框架。