第9章｜动态规划
Unit 03 · LeetCode #198 打家劫舍
不要问“这间房值不值得偷”，
要比较两段兼容前缀的最优结果。
本单元从 Unit 02 的“两条到达路径”升级到互斥选择：不偷当前房屋时继承前一段最优值；偷当前房屋时只能接到隔一间的兼容前缀。动画会持续显示两个候选各自覆盖的房屋范围。
已恢复上次学习位置阶段、动画、答题、代码和迁移进度均已恢复。
知识桥梁｜Unit 02 → Unit 03
Unit 02：选择更便宜的前驱
dp[i] 比较从 i-1 和 i-2 到达当前位置的累计费用。
路径来源 → 互斥决策
Unit 03：选择更高价值的方案
dp[i] 比较“不偷当前”的前缀最优值与“偷当前”的兼容前缀加当前金额。
本单元贯穿问题当前候选是“继承哪段前缀”，还是“必须包含当前房屋”？两者覆盖的房屋范围分别是什么？
LeetCode #198 原题题面转述、示例、约束与提交签名
题目要求
一条街上有若干房屋，nums[i] 表示第 i 间房屋中的金额。相邻房屋的报警系统相连，同一晚不能同时进入两间相邻房屋。返回在不触发报警的前提下能够取得的最大金额。
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
pass
约束
1 ≤ nums.length ≤ 100；0 ≤ nums[i] ≤ 400。
示例
输入：nums = [1,2,3,1]
输出：4
解释：选择第 1、3 间房屋，金额 1 + 3 = 4。
输出：4
解释：选择第 1、3 间房屋，金额 1 + 3 = 4。
输入：nums = [2,7,9,3,1]
输出：12
解释：选择第 1、3、5 间房屋，金额 2 + 9 + 1 = 12。
输出：12
解释：选择第 1、3、5 间房屋，金额 2 + 9 + 1 = 12。
目标复杂度
每间房屋处理一次，时间复杂度 O(n)；使用两个滚动摘要时，额外空间复杂度 O(1)。
前缀状态
dp[i] 表示前 i 间房屋的最优结果，而不是第 i 间的局部金额。
不偷当前
继承 dp[i-1]，当前房屋不进入方案。
偷当前
当前金额只能与 dp[i-2] 组合，保证相邻冲突被排除。
状态摘要
父问题只需要两段前缀的最大金额，不需要保存全部房屋集合。
互斥选择型 DP
—
本环节已完成
请停留观察当前状态，确认两个候选为什么互斥。