打家劫舍系列
本章目标：掌握打家劫舍系列的状态机 DP，从线性到环形到树形逐步进阶。
你将学到
- 线性 DP 的状态机设计
- 环形数组的处理（首尾不能同时取）
- 树形 DP（在树上做动态规划）
- 状态定义：偷/不偷两种状态
1. 概念
打家劫舍是动态规划的经典系列题目，核心模型是：相邻的房屋不能同时偷。这个约束可以抽象为一个通用的 DP 模式——对于每个位置，维护"选"和"不选"两个状态。
从简单到复杂：
- 线性版本（198）：一排房子，不相邻偷
- 环形版本（213）：首尾相连，首尾不能同时偷
- 树形版本（337）：房子排成二叉树，相邻层不能同时偷
2. 逐题精讲
LeetCode 198 · 打家劫舍（线性）
题意：一排房屋，每个有一定金额，不能偷相邻房屋，求最大金额。
思路：状态机 DP——dp[i] 表示偷到第 i 家时的最大金额。对每家有两个选择：偷（则不能偷上一家）或不偷。
python
def rob(nums):
"""状态机 DP"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# prev2 = 偷到 i-2 家的最大值，prev1 = 偷到 i-1 家
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = curr
return prev1更清晰的状态机写法：
python
def rob(nums):
# dp0 = 当前不偷的最大值，dp1 = 当前偷的最大值
dp0, dp1 = 0, 0
for num in nums:
# 今天不偷 = max(昨天不偷, 昨天偷)
# 今天偷 = 昨天不偷 + 今天金额
new_dp0 = max(dp0, dp1)
new_dp1 = dp0 + num
dp0, dp1 = new_dp0, new_dp1
return max(dp0, dp1)LeetCode 213 · 打家劫舍 II（环形）
题意：房子围成一圈，首尾相邻，求最大金额。
思路：环形意味着第一家和最后一家不能同时偷。拆成两个线性问题：
- 偷第一家 → 只考虑 [0, n-2]（不含最后一家）
- 不偷第一家 → 只考虑 [1, n-1]（不含第一家）
取两者的最大值。
python
def rob(nums):
if len(nums) == 1:
return nums[0]
def rob_linear(arr):
dp0, dp1 = 0, 0
for num in arr:
new_dp0 = max(dp0, dp1)
new_dp1 = dp0 + num
dp0, dp1 = new_dp0, new_dp1
return max(dp0, dp1)
# 偷第一家（不含最后）或不偷第一家（不含第一）
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))LeetCode 337 · 打家劫舍 III（树形）
题意：房子排成二叉树，相连的节点不能同时偷，求最大金额。
思路：树形 DP。对每个节点返回 [不偷该节点的最大值, 偷该节点的最大值]。
python
# 树节点定义
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob(root):
"""返回 [不偷当前节点的最大值, 偷当前节点的最大值]"""
def dfs(node):
if not node:
return [0, 0]
left = dfs(node.left)
right = dfs(node.right)
# 不偷当前：左右子树各取最优（偷或不偷）
not_rob = max(left[0], left[1]) + max(right[0], right[1])
# 偷当前：左右子树都不能偷
rob_cur = node.val + left[0] + right[0]
return [not_rob, rob_cur]
result = dfs(root)
return max(result[0], result[1])3. 复杂度
| 题目 | 时间 | 空间 |
|---|---|---|
| 198 | O(n) | O(1) |
| 213 | O(n) | O(1) |
| 337 | O(n) | O(h)，h 为树高 |
4. 易错点
- ⚠️ 环形问题不要忘了 len == 1 的边界
- ⚠️ 树形 DP 的返回值含义要清晰——
[0]是不偷当前，[1]是偷当前 - ⚠️ 不偷当前节点时，子节点可以偷也可以不偷，取较大值
- ⚠️ 偷当前节点时，子节点必须不偷，用
left[0]和right[0]
5. 推荐刷题清单
| 题号 | 题名 | 难度 | 关键 |
|---|---|---|---|
| 198 | 打家劫舍 | Medium | 线性 DP |
| 213 | 打家劫舍 II | Medium | 环形 DP |
| 337 | 打家劫舍 III | Medium | 树形 DP |
| 256 | 粉刷房子 | Medium | 类似状态机 |
| 152 | 乘积最大子数组 | Medium | 类似思维 |
延伸阅读
- LeetCode 官方
- 代码随想录
- 《算法导论》(CLRS)