今日刷题量：3
当前刷题总量：150
Easy: 59
Mid: 84
Hard: 7
Day39
解题思想
198 打家劫舍 I（线性数组）
- 约束：相邻不能同时偷。
- 状态：dp[i]：偷到第 i 家（0..i）为止的最大金额
- 转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- 不偷 i：沿用 dp[i-1]
- 偷 i：必须不偷 i-1，所以用 dp[i-2] + nums[i]
- 初始化
- dp[0]=nums[0]
- dp[1]=max(nums[0], nums[1])
- 优化：滚动变量 O(1) 空间
213 打家劫舍 II（环形数组）
- 约束：相邻不能偷，并且 首尾也相邻。
- 核心判断：第一家和最后一家不能同时偷 → 拆成两个线性问题（都用 198）：
- 只考虑 [0..n-2]（排除最后一家）
- 只考虑 [1..n-1]（排除第一家）
- 答案：max(rob(0..n-2), rob(1..n-1))
- 也可以用滚动变量
337 打家劫舍 III（树形）
- 约束：父子不能同时偷（相邻节点不能同时偷）
- 对每个节点 u 做两种状态：
- notRob[u]：不偷 u 的最大值
- rob[u]：偷 u 的最大值
- 转移：
- rob[u] = u.val + notRob[left] + notRob[right]
- notRob[u] = max(notRob[left], rob[left]) + max(notRob[right], rob[right])
- 答案：max(notRob[root], rob[root])
- 遍历方式：递归 DFS（天然后序），因为父节点需要先知道孩子的状态。
总结：
198：结构是线性 → 依赖 i-1、i-2
213：结构是环 → “断环成两条线”各跑一次 198
337：结构是树 → 每个点做“偷/不偷”两状态，后序合并
练习题目
198.打家劫舍（mid）：https://leetcode.cn/problems/house-robber/
213.打家劫舍II （mid）：https://leetcode.cn/problems/house-robber-ii/description/
337.打家劫舍III（mid）：https://leetcode.cn/problems/house-robber-iii/description/