BM78. 打家劫舍(一)
题目描述
你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金。 为了防止被发现，你不能偷相邻的两家。给定整数数组 nums， 请你计算在不被发现的前提下最多的偷窃金额。
输入格式
nums：int 型一维数组，表示每个房间的现金数额。
输出格式
返回 int 型，最多能偷到的金额。
示例
示例 1
输入：
nums = [1,2,3,4]
输出：
6
说明： 最优方案是偷第 2、4 个房间，金额 2 + 4 = 6。
示例 2
输入：
nums = [1,3,6]
输出：
7
说明： 最优方案是偷第 1、3 个房间，金额 1 + 6 = 7。
示例 3
输入：
nums = [2,10,5]
输出：
10
说明： 最优方案是偷第 2 个房间，金额 10。
解题思路
第一步：理解问题本质
一排房间，不能偷相邻的，求最大金额。这是「线性动态规划」的入门题： 每个房间只有「偷」和「不偷」两种选择，而选择会影响左右邻居。
第二步：状态与转移
设 dp[i] 表示「只考虑前 i 个房间时能偷到的最大金额」。对第 i 个房间：
- 不偷：金额等于前 i-1 个房间的最优值
dp[i-1]； - 偷：那么第 i-1 个房间一定不能偷，金额等于
dp[i-2] + nums[i]。
两者取大：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
答案是 dp[n]。复杂度 O(n) 时间、O(n) 空间。
第三步：滚动变量优化到 O(1)
转移只用到前两项 dp[i-1]、dp[i-2]，所以只需两个变量滚动：
prev, cur = 0, 0 # prev = dp[i-2], cur = dp[i-1]
for x in nums:
prev, cur = cur, max(cur, prev + x)
初始 prev = cur = 0 表示「还没有任何房间」，等价于 dp[0] = dp[-1] = 0。
完整代码实现
算法可视化 · 逐帧回放这道题的代码6 帧 · 录制输入 [1,2,3,4]
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
"""打家劫舍（不可偷相邻），滚动变量优化到 O(1) 空间"""
prev, cur = 0, 0 # prev = dp[i-2], cur = dp[i-1]
for x in nums:
prev, cur = cur, max(cur, prev + x)
return cur
示例推演
以 nums = [1,2,3,4] 为例：
| 处理 x | prev（dp[i-2]） | cur（dp[i-1]） | 新 cur = max(cur, prev+x) |
|---|---|---|---|
| 1 | 0 | 0 | max(0, 1) = 1 |
| 2 | 0 | 1 | max(1, 2) = 2 |
| 3 | 1 | 2 | max(2, 1+3) = 4 |
| 4 | 2 | 4 | max(4, 2+4) = 6 |
最终 cur = 6，与答案一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 一维 DP 数组 | O(n) | O(n) | 直观 |
| 滚动变量 | O(n) | O(1) | 推荐 |
易错点总结
1. 把「偷了 i 就必须不偷 i-1」写成减一
偷当前房间时，上一个能考虑的是 dp[i-2]，不是 dp[i-1] - nums[i-1]。
2. 初值用 nums[0]
用「两个变量都从 0 开始」的写法天然能处理空数组和单元素数组，
不需要单独把 nums[0] 拿出来当 dp 初值。
3. 混淆「环形」版本
本题是一排直线；如果房间首尾相连，那是 BM79， 需要拆成「不含首」和「不含尾」两个线性子问题。
扩展思考
- 环形版本见 BM79. 打家劫舍(二)。
- 树形版本（房间组成一棵树，不能偷相邻节点）用树形 DP。