打家劫舍问题：相邻房屋不能同时偷，如何偷到最多金额？

直接回答：一维 DP。设 dp[i] 为考虑前 i 家能偷到的最大金额：第 i 家要么不偷（dp[i−1]），要么偷（dp[i−2] + nums[i]），即 dp[i] = max(dp[i−1], dp[i−2] + nums[i])。由于只依赖前两项，用两个变量滚动即可，时间 O(n)、空间 O(1)。

展开解析：这题是「选与不选」型 DP 的最小模型，讲清楚状态定义（前缀最优解）和转移（当前决策与相邻约束）就抓住了 DP 的叙述套路：状态 → 转移 → 初始化 → 空间压缩。环形变体（首尾也算相邻）的解法是拆成两次线性 DP：不偷第一家 [0, n−2] 和不偷最后一家 [1, n−1] 取较大值。树上版本（打家劫舍 III，父偷子不能偷）是树形 DP：每个节点返回「偷/不偷」两个值，后序合并。追问方向：为什么不能贪心（构造反例 [2,7,9,3,1] 中贪心选 7+3 输给 2+9+1）、如何把转移方程推广到「间隔至少 k 家」。

示例：

def rob(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1