LeetCode 213. 打家劫舍 II

约 5 分钟
文章信息 17 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 腾讯 字节 阿里 华为 亚马逊 美团 拼多多 百度 快手 滴滴 商汤
标签
数组 动态规划

题目描述

✅ 213. 打家劫舍 II

image-20260928203955944

image-20260928203955945

题意分析

每间房有一定金额，不能同时选择相邻两间房。房屋首尾相连成环，所以第一间和最后一间也相邻，要求在所有合法选择中取得最大总金额。

房屋金额非负，可以跳过任意房屋，也不要求一定选择首尾中的某一间。只有一间房时，直接选择这一间即可，不应把它误当成与自身冲突。

解法：拆环后线性动态规划

核心思路

[!blue]

环比普通直线只多了一条首尾相邻的限制。任意合法方案不可能同时选择第一间和最后一间，因此至少会放弃其中一端：要么只在 [0, n - 2] 内选择，要么只在 [1, n - 1] 内选择。

分别求这两个区间的最优解再取最大，就不会漏掉合法方案。每个区间都已经排除一个端点，区间内只剩普通的线性相邻限制，因此得到的方案也一定满足原环形要求。两个范围可以都覆盖“首尾都不选”的方案，但这里只取最大值，不会重复相加。

对一个线性区间，按最后一间是否选择分类。若不选当前房，收益就是前一位置的最优值；若选择当前房，前一间必须跳过，收益是前两间之前的最优值加上当前金额。二者取大，便得到当前前缀的最优收益。

用 preOne 表示处理当前房之前、截至前一房的最优值，preTwo 表示截至前两房的最优值。先算 cur = max(preOne, preTwo + nums[i])，再滚动保存。两次区间计算各自从 0 开始，不共享上一次的状态。

只有一间房时不能按上述方式拆，否则两个区间都为空，因此入口单独返回这一间的金额。两间及以上都可以使用相同的双区间计算。

解题步骤

  1. 若只有一间房，返回它的金额。
  2. 编写 robRange(nums, left, right)，处理包含左右端点的线性区间，两个历史最优值都初始化为 0。
  3. 从左到右遍历区间，每轮比较“不选当前房”与“选当前房并跳过前一间”，先求 cur 再更新两个历史状态。
  4. 对 [0, n - 2] 求解，表示不选最后一间；对 [1, n - 1] 求解，表示不选第一间。
  5. 返回两个线性结果中的较大值。

代码实现

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;

        if (n == 1) {
            return nums[0];
        }

        // 首尾不能同时选，分别排除一端即可覆盖全部合法方案。
        int skipLast = robRange(nums, 0, n - 2);
        int skipFirst = robRange(nums, 1, n - 1);

        return Math.max(skipLast, skipFirst);
    }

    private int robRange(int[] nums, int left, int right) {
        int preTwo = 0;
        int preOne = 0;

        for (int i = left; i <= right; i++) {
            // 不选当前位置沿用前一最优，选择它只能连接前两间的最优。
            int cur = Math.max(preOne, preTwo + nums[i]);

            preTwo = preOne;
            preOne = cur;
        }

        return preOne;
    }
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }

    // 首尾不能同时选，分别排除一端即可覆盖全部合法方案。
    skipLast := robRange(nums, 0, n-2)
    skipFirst := robRange(nums, 1, n-1)
    if skipLast > skipFirst {
        return skipLast
    }
    return skipFirst
}

func robRange(nums []int, left int, right int) int {
    preTwo, preOne := 0, 0
    for i := left; i <= right; i++ {
        // 不选当前位置沿用前一最优，选择它只能连接前两间的最优。
        cur := preOne
        if preTwo+nums[i] > cur {
            cur = preTwo + nums[i]
        }
        preTwo, preOne = preOne, cur
    }
    return preOne
}

复杂度分析

  • 时间复杂度：$O(n)$，两个长度不超过 $n$ 的区间各扫描一次。
  • 空间复杂度：$O(1)$，线性 DP 只保留前两个状态。

关键点总结

[!green]

  • 至少排除一个端点，就能消除环的额外限制；两个区间共同覆盖全部合法方案。
  • 排除一端不代表必须选择另一端，首尾都不选也属于允许的情况。
  • 线性递推按选或不选当前房分类，两个历史最优值只需滚动保存。

易错点总结

[!yellow]

  • 直接把整个数组作为直线计算，可能同时选中首尾两间，违反环形相邻限制。
  • 忽略单间情况，会拆出两个空区间并错误返回 0。
  • 拆分区间仍同时包含首尾，等于没有消除冲突；两个闭区间的端点要分别排除一侧。
  • 先覆盖历史状态再计算当前值，会混用新旧结果，甚至等价于选中了相邻两间。
  • 两次区间求解复用未重置的状态，会把互不属于同一方案的收益串在一起。
  • 把两个结果相加，或强制选择未排除的端点，都改变了“在合法方案中取最大”的含义。

相似题目

题目 难度 关联与区别
198. 打家劫舍 中等 本题通过分别排除首项和末项，转化为两次线性打家劫舍。
740. 删除并获得点数 中等 同样化为相邻类别不能同时选择，原题先按数值聚合收益，本题邻接来自环形位置。
337. 打家劫舍 III 中等 比较选择当前元素与跳过当前元素的最优值；本题拆开环形首尾冲突的两种情况，该题树上分别返回选根与不选根的结果。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/89469061
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！