198. 打家劫舍 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/house-robber/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例 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 <= 100
- 0 <= nums[i] <= 400
题目详细分析
- 数据范围：长度最大 100，金额最大 400，结果适合用 int 存储。
- 核心约束：不能偷相邻的两间房。这是典型的”选/不选”模型。
- 边界条件：数组长度为 1 时只能偷这一家；长度为 2 时取较大者。
- 隐藏条件：隔一间偷不一定是最优——可以间隔多间，只在相邻约束下最大化总和。
小白版直白理解
想象你是一个小偷，街道上一排房子不能连续偷两家（警报会响）。那你怎么决定偷哪些家呢？其实很简单：
- 走到某一家门口，你有两个选择：不偷这家，那就保持上一家时的最大收益；偷这家，那就加上上上家时的最大收益（因为隔壁不能偷）。
- 每次都在两个选项中取大的那个，走到头就是答案。就像游戏里每步选”拿”或”不拿”两种分支。
解题思路
思路一：动态规划（推荐）
核心洞察：对于第 i 间房，如果偷，则 i-1 不能偷，总金额 = dp[i-2] + nums[i-1]；如果不偷，总金额 = dp[i-1]。两者取大。
DP 五步法：
- dp 定义：
dp[i]表示前 i 间房屋（即 nums[0..i-1]）能偷到的最高金额 - 递推公式：
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]) - 初始化：
dp[0] = 0（没有房子），dp[1] = nums[0]（只有一间房） - 遍历顺序：从 i=2 到 n，正序
- 举例验证：nums=[2,7,9,3,1] → dp[1]=2, dp[2]=max(2,7)=7, dp[3]=max(7,2+9=11)=11, dp[4]=max(11,7+3=10)=11, dp[5]=max(11,11+1=12)=12 ✓
def rob(nums):
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * (n + 1)
dp[1] = nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n]思路二：空间优化 DP（滚动变量）
只用两个变量代替整个 dp 数组。
def rob(nums):
prev2 = 0 # dp[i-2]
prev1 = 0 # dp[i-1]
for num in nums:
# cur = max(不偷, 偷)
cur = max(prev1, prev2 + num)
prev2, prev1 = prev1, cur
return prev1思路三：奇偶动态规划（拓展思路）
维护奇偶索引累积金额，本质也是选/不选思想。
def rob(nums):
odd_sum = even_sum = 0
for i, num in enumerate(nums):
if i % 2 == 0:
even_sum = max(even_sum + num, odd_sum)
else:
odd_sum = max(odd_sum + num, even_sum)
return max(even_sum, odd_sum)易错点
- 空数组处理：题目提示长度 >= 1，但防御性编程应处理空数组。
- 初始化值：
dp[0]是 0（没有房子），dp[1]是 nums[0]，不是 0。 - 仅有一间房：直接返回 nums[0]，不能走递推（dp[2] 越界）。
- 递推公式混淆：不要写成
dp[i] = max(dp[i-1], dp[i-2] + nums[i])，注意 nums 索引偏移。
框架提炼
线性选/不选 DP 模板：
def linear_select(nums):
prev2 = 0 # 前前状态
prev1 = 0 # 前一个状态
for x in nums:
cur = max(prev1, prev2 + x) # 不选 vs 选
prev2, prev1 = prev1, cur
return prev1这种”选/不选”结构适用于一系列互斥决策问题，核心是定义清楚”选”的收益来源和”不选”的兜底。
关联题目
- 70-爬楼梯 — 相同的线性递推结构，递推从加法变为取 max
- 213-打家劫舍 II — 本题的环形变体，拆成两个线性问题
- 337-打家劫舍 III — 树形 DP，二叉树上的选/不选模型