打家劫舍
House Robber
一排房屋各藏一定金额，相邻两间不能同时偷，求能偷到的最高金额。
在力扣中练习题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
解题思路
一维 DP · 最后一间抢不抢
每间房只有两种命运：抢它，或者跳过它
最直接的想法是把所有“不连续”的房间组合都试一遍，共 2^n 种，n 稍大就不可行。
换个角度，只看最后一间房：要么不抢，答案就是前 i-1 间的最高金额；要么抢，那么前一间一定不能抢，能接上的只有前 i-2 间。于是
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
自拟主例 nums = [4,9,3,1,8,6]。第 3 间价值 3，抢它要放弃第 2 间的 9，不划算；第 5 间价值 8，接上 dp[2]=9 得到 17，比不抢的 10 更划算。
dp[1] = max(4, 9) = 9；前两间只能选一间。
- dp[1]
- 9
dp[i] = 只考虑前 i+1 间房时能拿到的最高金额；相邻两间不能同时抢
dp[1]=9边界是前两间：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。从第 2 间开始，每个状态只往前看两级，所以按 i 从小到大递推即可。
第 3 间：不抢沿用 9；抢则接上 dp[1] = 9，得 10。取 10。
- i
- 3
- dp[i]
- 10
dp[i] = 只考虑前 i+1 间房时能拿到的最高金额；相邻两间不能同时抢
dp[3]=max(dp[2], dp[1] + nums[3])max(9, 9 + 1)=10选中 dp[1] +1
时间 O(n)。注意 dp[i] 表示“前 i+1 间”的整体最优，不是“必须抢第 i 间”的最优。
易错点
- 按奇偶位置分组求和：[4,9,3,1,8,6] 的答案 17 是 9+8，并非简单的奇偶位。
- dp[1] 直接写 nums[1]：当 nums[0] 更大时，前两间的最优会算错。
- n == 1 时仍去访问 dp[1] 或 nums[1]，数组越界；先特判。
滚动变量 · O(1) 空间
只留 dp[i-2] 和 dp[i-1]，边扫边滚
时间相同，只保留前两个状态，空间 O(1)；代价是失去完整 dp 表，不能直接回溯选了哪些房子。
转移只读取前两级，更早的状态永远不会再用到，所以不需要整个数组。
用 prev2、prev1 分别代表 dp[i-2]、dp[i-1]。每读一间房 x：
cur = max(prev1, prev2 + x)
prev2 = prev1
prev1 = cur
两个变量必须先算 cur，再依次后移；如果先覆盖 prev1，旧的 dp[i-1] 就丢了。
空间 O(1)，时间仍是 O(n)。若题目还要求输出具体抢了哪些房子，就要额外保存选择，不能只留两个数。
- 1prev2 = 0，prev1 = 0。
- 2遍历每间房：cur = max(prev1, prev2 + x)。
- 3prev2 = prev1，prev1 = cur。
- 4返回 prev1。
易错点
- 三个变量更新顺序写反：先用 cur 覆盖 prev1，再更新 prev2，会丢掉上一轮状态。
- 把 prev2 + x 写成 prev2 + nums[i] 却忘了 i 的对应关系，滚动变量与下标容易错位。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [4,9,3,1,8,6]只有一间房时只能抢它：dp[0] = 4。
- dp[0]
- 4
dp[i] = 只考虑前 i+1 间房时能拿到的最高金额；相邻两间不能同时抢
dp[0]=4查看 C++ 代码
延伸阅读
- 打家劫舍的核心是“相邻互斥”的选择约束；环形房屋（213）需要把首尾分开讨论两次。
- 树形打家劫舍（337）把同样的“抢 / 不抢”状态搬到二叉树上，每个节点返回一对值。