手帐 Blog

主题

复盘 · LC 198 打家劫舍 ​

题目 ​

题意 ​

给定非负整数数组 nums，nums[i] 表示第 i 家能偷到的金额。相邻两家不能同时偷，求能偷到的最大总金额。

  • 至少有一户人家；金额非负。
  • 边界：[1] 直接返回 1；全 0 返回 0；「隔一家偷」比「全偷偶数位」更优时要靠 DP 比较。

涉及算法 ​

标签一句话
一维 DPdp[i] = 到第 i 家为止的最大收益
空间优化只依赖前两项 → 两个滚动变量

教程对照：21 · DP 入门 · 一维 精讲题即本题，转移式 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

评价我的解法 ​

注释写「没有思路，看了题解」——但落笔的正是教程里的滚动变量版，和官方最优骨架一致。

我的代码（摘自 198-打家劫舍/index.js，不含测例）：

javascript
var rob = function (nums) {
  let pre1 = 0,
    pre2 = 0;
  for (const num of nums) {
    const tmp = pre1;
    pre1 = Math.max(pre1, pre2 + num);
    pre2 = tmp;
  }
  return pre1;
};

对在哪

  1. 状态压缩正确：pre1 相当于「上一家的最优」，pre2 是「上上一家的最优」，每轮 Math.max(不偷这家, 偷这家) 语义清晰。
  2. 复杂度到位：时间 O(n)，空间 O(1)；没有开 dp 数组，面试加分。
  3. 变量更新顺序对：先 tmp = pre1 再滚动，避免覆盖旧值。

糙在哪

  1. 命名：教程用 prev1/prev2 或 cur/prev2 更直观；pre1/pre2 口述时要额外解释「哪个是更近的一户」。
  2. 残留注释 // pre1 无信息量，可删。
  3. 缺边界口述：代码靠初值 0,0 隐式处理了 nums 为空（题目保证非空）；面试可一句带过「空数组返回 0」。

小结：实现已是标准答案；缺口在独立推出转移式，不是写法。明天应能在不看解的情况下，从「偷 / 不偷」两分支写出这 6 行。

最佳题解 ​

与当前写法等价，仅命名贴近教程：

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  let prev2 = 0;
  let prev1 = 0;
  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
};
  • 时间 O(n)，空间 O(1)。
  • 为何够用：每家只依赖前两家最优，无需整表；比递归 + 记忆化更省栈、比二维更清晰。

若要从零推导，口述模板：「到 i 为止最大收益 = max(不偷 i → 沿用 i-1，偷 i → prev2 + nums[i])」。

关联题目 ​

题为何相关
213. 打家劫舍 II首尾相邻成环，拆成两段 198
337. 打家劫舍 III树形 DP，同一「选/不选」思想
746. 使用最小花费爬楼梯一维 DP + 双变量滚动，结构更像爬楼梯

一句话带走 ​

打家劫舍：每家 max(不偷沿用 prev1，偷则 prev2 + 金额)，两个变量滚动即可，不必开数组。