动态规划是解决打家劫舍问题最自然高效的方法，核心是定义dp[i]为前i+1间房能偷到的最高金额，状态转移方程为dp[i]=max(dp[i−1], dp[i−2]+nums[i])，可优化至O(1)空间。
动态规划是解决打家劫舍问题最自然、高效的方法。核心在于把“要不要偷第 i 间房”这个局部决策，和前面已知的最优结果关联起来，避免重复尝试所有组合。
明确状态定义和转移逻辑
设 dp[i] 表示考虑前 i+1 间房（即下标 0 到 i）时，能偷到的最高金额。
对第 i 间房，只有两种互斥选择：
- 不偷它：最大金额就是 dp[i−1]
- 偷它：必须跳过 i−1，只能加上 dp[i−2] + nums[i]
因此状态转移方程为：dp[i] = max(dp[i−1], dp[i−2] + nums[i])
处理边界和初始化
数组长度很小时需单独处理：
- 空数组 → 返回 0
- 只有一个数 → 返回 nums[0]
- 两个数 → 返回 max(nums[0], nums[1])
对应地，dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])，之后从 i = 2 开始递推。
空间优化到常数级别
因为每次只用到 dp[i−1] 和 dp[i−2]，不需要整个数组。用两个变量滚动更新即可：
- 用 pre 记录 dp[i−2]
- 用 cur 记录 dp[i−1]
- 每轮计算新值 tmp = max(cur, pre + nums[i])，再更新 pre = cur，cur = tmp
这样空间复杂度从 O(n) 降到 O(1)，代码更简洁，也更适合面试手写。
验证思路靠小例子推导
拿 [2, 7, 9, 3, 1] 来试：
- i=0: dp[0] = 2
- i=1: dp[1] = max(2,7) = 7
- i=2: dp[2] = max(7, 2+9) = 11
- i=3: dp[3] = max(11, 7+3) = 11
- i=4: dp[4] = max(11, 7+1) = 12 ✅
结果 12 符合预期（偷第0、2、4间：2+9+1），说明状态设计和转移是可靠的。
