LeetCode 198. 打家劫舍

约 4 分钟
文章信息 23 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 LeetCode 75 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 亚马逊 美团 拼多多 京东 网易 快手 滴滴 携程 虾皮
标签
数组 动态规划

题目描述

✅ 198. 打家劫舍

image-20260928194604011

题意分析

数组中每个非负整数表示一间房屋的金额，房屋按一条直线排列。选择若干间房屋，使任意两间被选中的房屋都不相邻，并让所选金额之和最大；返回最大总额，不需要返回选择方案。

不要求固定隔一间选一间，也不要求选够某个数量，必要时可以连续跳过多间。首尾房屋没有额外的环形相邻关系，是否冲突只看原数组中是否紧挨着。

解法：滚动变量动态规划

核心思路

[!blue]

处理一段房屋时，最后一间只有选或不选两种情况。令 f(i) 表示只考虑下标 0 到 i 的房屋时能得到的最大金额，强调“考虑过”，并不要求一定选择第 i 间。

如果不选第 i 间，所有选择都位于前面的房屋，最佳收益就是 f(i - 1)。如果选第 i 间，则第 i - 1 间不能选，而更前面的房屋只需满足原来的不相邻约束，最佳收益就是 f(i - 2) + nums[i]。两种情况覆盖所有合法方案，分别取各自最优后再比较，得到 f(i) = max(f(i - 1), f(i - 2) + nums[i])。

转移只用到前两个状态，可以用 pre、cur 替代整个数组。处理 nums[i] 之前，pre 保存 f(i - 2)，cur 保存 f(i - 1)；先用这两个旧状态计算 next，再执行 pre = cur、cur = next，它们就变成下一轮需要的前两个状态。

初始化 pre = cur = 0，表示尚未考虑任何房屋时收益为零，也把第一间之前不存在的两个前缀统一当作空范围。第一间和第二间因此可以使用同一条转移，无需单独访问两个起始元素。每轮都保留选与不选的最优结果，避免根据眼前某一间金额作局部决定。

解题步骤

  1. 令 pre = 0、cur = 0，从左到右遍历每间房屋的金额 num。
  2. 计算 next = max(cur, pre + num)：前者表示跳过当前房屋，后者表示选择当前房屋并避开前一间。
  3. 保存好 next 后，先将旧 cur 放入 pre，再用 next 更新 cur。
  4. 遍历结束时，cur 已经表示整个数组的最优收益，返回它。

代码实现

class Solution {
    public int rob(int[] nums) {
        int pre = 0;
        int cur = 0;

        for (int num : nums) {
            // 不选当前房屋沿用前一状态，选它则只能连接前两间的最优值。
            int next = Math.max(cur, pre + num);

            pre = cur;
            cur = next;
        }

        return cur;
    }
}

func rob(nums []int) int {
    pre := 0
    cur := 0

    for _, num := range nums {
        // 不选当前房屋沿用前一状态，选它则只能连接前两间的最优值。
        next := cur
        if pre+num > next {
            next = pre + num
        }
        pre = cur
        cur = next
    }
    return cur
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为房屋数量，每间房屋只做一次状态转移。
  • 空间复杂度：$O(1)$，只保留两个历史状态及本轮结果。

关键点总结

[!green]

  • 前缀最优值不要求选择前缀末尾，才能完整表示“当前不选”的情况。
  • 选择当前房屋时连接前两个位置的最优结果，确保不会同时选择相邻房屋。
  • 先计算新值再滚动旧值，保持 pre、cur 在每轮开始时的含义。
  • 最优方案不一定固定选择奇数位或偶数位，必须逐个前缀保留两种选择。

易错点总结

[!yellow]

  • 先更新 pre 再计算 next，会把前一间之前的范围扩大一位，可能把相邻房屋的收益连在一起。
  • 只保留 pre + num，会强制选择当前房屋，丢掉跳过它可能更优的方案。
  • 把 cur 理解为“一定偷上一间”，与实际转移的前缀最优定义不符。
  • 只比较相邻两间的金额或固定选择一组奇偶位置，不能覆盖所有合法的不相邻组合。
  • 直接读取 nums[1] 做初始化却未处理单间房屋，会越界；从两个零状态开始不需要这种分支。

相似题目

题目 难度 关联与区别
213. 打家劫舍 II 中等 增加首尾相邻条件后，不能同时选择两端，需要拆成两条线性区间。
337. 打家劫舍 III 中等 把线性相邻限制扩展到父子节点不能同时选择，状态仍是选与不选。
740. 删除并获得点数 中等 比较选择当前元素与跳过当前元素的最优值；本题禁止选择相邻房屋，该题按值累计收益后禁止选择相邻值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/30989935
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！