跳转至

198. 打家劫舍（House Robber）

频次 ★★★★★ · 难度 🟢 · 高频：全厂

题目

一排房屋，每个有现金。不能偷相邻的，求最大偷盗金额。

示例： 

输入: nums = [2,7,9,3,1]
输出: 12  （偷 2+9+1）

思路

一维 DP：到第 i 间房时，最大金额 = max(偷这间 + i-2 的最佳，不偷这间 = i-1 的最佳)。

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

空间优化：滚动两个变量代替数组。

代码

public int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;    // dp[i-2], dp[i-1]
    for (int n : nums) {
        int cur = Math.max(prev1, prev2 + n);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

前缀世界扩大链——dp[0] 为什么必须"真"（实测首坑）

dp[i] = 看第 0..i 栋的最优，"延续 dp[i-1]（不偷新栋）+ 新栋入伙 dp[i-2]+nums[i]"
推论：dp 单调不减（世界只大不小）；转移两加数 = "延续"与"入伙"（同 518"旧值=合法过去、新值=合法新增"）
  • dp[0] ≠ min(nums[0],nums[1])：dp[0] 的世界只有第 0 栋 → 必须 =nums[0]（反例 [5,1,10]：5 vs 1，错版全链 -4）
  • 两格语义独立说出（"前 1 栋"/"前 2 栋"）——与 47"used 身份"、322"dp[0] 语义"同源：dp 地基格永远是"前缀语义"，不是锚位妙手
  • harness 盲区预警：min/max 碰巧等效的用例抓不住——地基错误要靠手推反例，不能全信绿

复杂度

  • 时间：O(n)
  • 空间：O(1)

边界条件

  • 空数组：返回 0
  • 单房屋：返回该房屋金额

变式

易错点

  • dp[i] 初始化 全部为 0 而非其它值——因为金额可能为 0 但不会为负
  • prev2 初始 0 是状态定义使然（没房屋时金额 = 0）

面试追问

  • 如果房屋排成环？ 拆成两个子问题：偷第一家不偷最后一家 / 偷最后一家不偷第一家，见 213

关联题