graph LR A[打家劫舍] --> B[线性: 选/不选] A --> C[环形: 首尾互斥] A --> D[树形: 子树取舍]
"打家劫舍"是线性 DP 最经典的入门模型族，三道题层层递进：
| 题目 | 结构 | 核心约束 |
|---|---|---|
| LC 198. 打家劫舍 | 一排房屋（线性） | 相邻不能偷 |
| LC 213. 打家劫舍 II | 环形房屋 | 相邻不能偷 + 首尾相邻 |
| LC 337. 打家劫舍 III | 二叉树 | 直接父子不能偷 |
共同本质：在一个有"相邻冲突"约束的结构上，选取权值最大的独立子集。
dp[i] = 考虑前 i 间房屋能偷到的最大金额。
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
// 不偷第i间 // 偷第i间（则第i-1间不能偷）
决策直觉：站在第 i 间门口，只有两个选择——跳过它（继承 dp[i-1]），或者偷它（拿 dp[i-2] + 当前金额）。
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
int[] dp = new int[n + 1];
dp[1] = nums[0];
for (int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[n];
}dp[i] 只依赖前两个值，用两个变量滚动：
function rob(nums: number[]): number {
let prev2 = 0, prev1 = 0;
for (const num of nums) {
const cur = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}复杂度：时间 O(n)，空间 O(1)。
首尾相邻意味着第一间和最后一间不能同时偷。分两种情况取最大值：
答案 = max(
rob(nums[0..n-2]), // 偷第一间，不偷最后一间
rob(nums[1..n-1]) // 不偷第一间，可以偷最后一间
)
两种情况覆盖了所有合法方案（第一间和最后一间至少有一个不偷）。
function rob(nums: number[]): number {
const n = nums.length;
if (n === 1) return nums[0];
if (n === 2) return Math.max(nums[0], nums[1]);
return Math.max(
robRange(nums, 0, n - 2), // 含首不含尾
robRange(nums, 1, n - 1), // 含尾不含首
);
}
function robRange(nums: number[], lo: number, hi: number): number {
let prev2 = 0, prev1 = 0;
for (let i = lo; i <= hi; i++) {
const cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}易错：n=1 和 n=2 的边界必须特判，否则拆分会出错。
对每个节点返回一个二元组：
rob(node) = [不偷node的最大收益, 偷node的最大收益]
不偷 node：左右子节点可偷可不偷
→ max(左偷,左不偷) + max(右偷,右不偷)
偷 node：左右子节点都不能偷
→ node.val + 左不偷 + 右不偷
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
int rob = node.val + left[0] + right[0];
return new int[]{notRob, rob};
}复杂度：时间 O(n)，每个节点访问一次；空间 O(h) 递归栈。
| 版本 | 结构 | "相邻"的定义 | 技巧 |
|---|---|---|---|
| 线性 | 数组 | 下标相邻 | 滚动变量 |
| 环形 | 数组首尾相连 | 下标相邻 + 首尾 | 拆两段 |
| 树形 | 二叉树 | 父子关系 | 后序遍历返回二元组 |
通用模式：「选或不选」+ 冲突约束 → 状态设计为 (不选当前, 选当前)。
如果不能偷距离 ≤ k 的房屋：dp[i] = max(dp[i-1], dp[i-k-1] + nums[i])。
"环形链表上的打家劫舍"：同样拆成两段线性问题。
LC 740：选了值 x 就要删除所有 x±1。排序/桶化后就是打家劫舍。
dp[i] 对应 nums[i-1]，初始化 dp[1]=nums[0]。每间门口二选一，跳过继承偷加钱； 环形拆成两段跑，树上后序返双元。