打家劫舍：从线性到树形，彻底玩转动态规划

蔚蓝WEILANX2026-03-062026-03-06

哈喽，大家好呀，我是蔚蓝🥰！今天我们来聊聊 DP 专题里最像「犯罪现场模拟」的一个系列——打家劫舍 (House Robber)。

很多小伙伴刚接触动态规划时，觉得这题挺逗，怎么还教人「偷东西」呢？其实，这道题的精髓不在于「偷」，而在于如何处理邻居之间的制约关系。

今天这一篇，我把笔记里从简单的路边排房，到成环的社区，再到那棵让人抓狂的「老大的办公楼」，全部梳理清楚。核心代码都是最纯粹的 Java 版，保证你看完就能上手！

1. 关卡一：线性社区 (HR I) —— 别碰隔壁老王

如果你面前是一排房子，每家都有金币，但只要你连着偷两家，警报就会响。这就是最经典的一维 DP。

很多人第一反应是：我选奇数位还是偶数位？大错特错！ 算法的世界里，你要做的是不断决策。

一眼识别状态：走到第 i 家房门口，我只有两个选择：
1. 偷！那我不仅能拿这家的钱，还得保证前一家没动身。
2. 不偷！ 那我能拿到的最大值，就是我走到前一家门口时的战果。

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0]; // 只有一个房子，偷就完事了

        // dp[i] 代表走到第 i 间房能偷到的最高金额
        int[] dp = new int[nums.length];
        dp[0] = nums[0]; // 只有第一家
        dp[1] = Math.max(nums[0], nums[1]); // 在前两家之间选个大的

        for (int i = 2; i < nums.length; i++) {
            // 决策时刻：是偷这一家（加上前前家的钱），还是跳过这一家（拿前一家的钱）
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
      
        return dp[nums.length - 1];
    }
}

2. 关卡二：社区成环 (HR II) —— 咬到尾巴的贪吃蛇

当这排房子首尾相连变成一个社区时，事情变邪乎了：你偷了第一家，最后一家就不能动。

这其实是一个 「破圈」 的过程。我们不需要复杂的联立方程，直接暴力拆解成两种情况：

不管最后一家：只算 [第一家, 倒数第二家]。
不管第一家：只算 [第二家, 最后一家]。

最后两者取大值，完美化解死循环。

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
      
        // 既然首尾相连，我们就分场景讨论
        int result1 = robRange(nums, 0, nums.length - 2); // 场景 1：不考虑最后一家
        int result2 = robRange(nums, 1, nums.length - 1); // 场景 2：不考虑第一家
      
        return Math.max(result1, result2);
    }

    private int robRange(int[] nums, int start, int end) {
        if (start == end) return nums[start];
      
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
      
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
      
        return dp[end];
    }
}

3. 关卡三：树形办公楼 (HR III) —— 擒贼先擒王

这是本系列的终极变体。房子不再是排成队，而是长成了一棵二叉树。邻居不再是左右，而是「父与子」。

这时候，线性遍历失效了，我们需要派侦察兵去深度优先搜索 (DFS)，并且要按照 「由下至上」 的财务汇报逻辑（后序遍历）。

：每个节点都要向老板汇报两个数字：{我不偷能拿多少, 我偷能拿多少}。

class Solution {
    public int rob(TreeNode root) {
        int[] res = robAction(root);
        // 最后在根节点的“偷”与“不偷”中选个最大值
        return Math.max(res[0], res[1]);
    }

    private int[] robAction(TreeNode root) {
        if (root == null) return new int[]{0, 0}; // 空树，汇报全是 0
    
        // 递归拿到左边和右边小弟的汇报（后序遍历）
        int[] left = robAction(root.left);
        int[] right = robAction(root.right);
    
        // 1. 如果我偷：那我左右孩子只能乖乖呆着，绝对不能偷
        int v1 = root.val + left[0] + right[0];
    
        // 2. 如果我不偷：那左右孩子随你们便，偷不偷都行，我选钱多的路子
        int v0 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    
        return new int[]{v0, v1}; // 向上级汇报我的成果
    }
}