打家劫舍 II / House Robber II

怎样从“房子围成一圈，第 0 间和最后一间也相邻。nums=[2,7,9,3,1] 答案 11；反例 nums=[2,3,2] 首尾两个 2 相邻不能同时偷，答案 3。”推导出 线性 DP · 环形拆两条线，并证明每次状态变化都不会漏掉答案？

中心结论：最优解一定不同时含首尾，于是把环拆成两条线性数组：A=nums[0..n-2]（去尾）、B=nums[1..n-1]（去首），各跑一遍 LC198 的 robRange，answer=max(robRange A, robRange B)；n==1 特判直接返回 nums[0]。

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

在本站主例中，房子围成一圈，第 0 间和最后一间也相邻。nums=[2,7,9,3,1] 答案 11；反例 nums=[2,3,2] 首尾两个 2 相邻不能同时偷，答案 3。

算法最终需要得到或观察：nums=[2,7,9,3,1] 时 robRange(0,3)=11、robRange(1,4)=10、answer=max(11,10)=11。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 robRange 里 pre=前前一间最优、cur=前一间最优、next=max(cur, pre+nums[i]) 三个滚动变量，外加两趟结果与最终 answer。
3. 3转移每一步按照 最优解一定不同时含首尾，于是把环拆成两条线性数组：A=nums[0..n-2]（去尾）、B=nums[1..n-1]（去首），各跑一遍 LC198 的 robRange，answer=max(robRange A, robRange B)；n==1 特判直接返回 nums[0]。
4. 4收尾读取 nums=[2,7,9,3,1] 时 robRange(0,3)=11、robRange(1,4)=10、answer=max(11,10)=11。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：robRange 里 pre=前前一间最优、cur=前一间最优、next=max(cur, pre+nums[i]) 三个滚动变量，外加两趟结果与最终 answer。

这一题是第 198 题的加强版。不过这次是在一个环形的街道中，即最后一个元素和第一个元素是邻居，在不触碰警报的情况下，问能够窃取的财产的最大值是多少？ 解题思路和第 198 完全一致，只需要增加额外的一个转换。由于首尾是相邻的，所以在取了第一个房子以后就不能取第 n 个房子，那么就在 [0,n - 1] 的区间内找出总价值最多的解，然后再 [1,n] 的区间内找出总价值最多的解，两者取最大值即可。

最优解一定不同时含首尾，于是把环拆成两条线性数组：A=nums[0..n-2]（去尾）、B=nums[1..n-1]（去首），各跑一遍 LC198 的 robRange，answer=max(robRange A, robRange B)；n==1 特判直接返回 nums[0]。

执行过程中持续维护：robRange 里 pre=前前一间最优、cur=前一间最优、next=max(cur, pre+nums[i]) 三个滚动变量，外加两趟结果与最终 answer。

正确性依赖以下不变量：首尾相邻 → 最优解最多含其一；去尾的方案全在 A、去首的方案全在 B，两类穷尽所有合法解；首尾都不偷的方案同属 A、B 已被自动覆盖；robRange 内每步 cur 恒为该线到当前房的最大收益。n 是房子数量。

面试时可以压缩为：这是 LC198 的环形版，唯一区别是第 0 间和最后一间也相邻、不能同时偷。所以最优解必落在“不偷尾”或“不偷首”两种情况：拆成 A=nums[0..n-2]、B=nums[1..n-1] 两条线性数组，各跑一遍 robRange（pre/cur 滚动、next=max(cur,pre+nums[i])），取 max 即答案；n==1 特判返回 nums[0]。时间 O(n)，空间 O(1)，n 是房子数量。

落到当前题，执行机制可以压缩为：最优解一定不同时含首尾，于是把环拆成两条线性数组：A=nums[0..n-2]（去尾）、B=nums[1..n-1]（去首），各跑一遍 LC198 的 robRange，answer=max(robRange A, robRange B)；n==1 特判直接返回 nums[0]。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入房子围成一圈，第 0 间和最后一间也相邻。nums=[2,7,9,3,1] 答案 11；反例 nums=[2,3,2] 首尾两个 2 相邻不能同时偷，答案 3。 因为：最优解一定不同时含首尾，于是把环拆成两条线性数组：A=nums[0..n-2]（去尾）、B=nums[1..n-1]（去首），各跑一遍 LC198 的 robRange，answer=max(robRange A, robRange B)；n==1 特判直接返回 nums[0]。
2. 2dp[i] = 前 i 间能偷的最大金额准备扫描每间房。 因为：偷 i 则不能偷 i-1。
3. 3第 0 间:偷 2 vs 不偷 0 → 2滚动更新 prev2/prev1。 因为：线性 DP O(n)。
4. 4第 1 间:偷 3 vs 不偷 2 → 3滚动更新 prev2/prev1。 因为：线性 DP O(n)。
5. 5第 2 间:偷 4 vs 不偷 3 → 4滚动更新 prev2/prev1。 因为：线性 DP O(n)。
6. 6最大金额 4返回 prev1。 因为：O(n) O(1) 空间。
7. 7dp[i] = 前 i 间能偷的最大金额准备扫描每间房。 因为：偷 i 则不能偷 i-1。
8. 8收尾与复杂度nums=[2,7,9,3,1] 时 robRange(0,3)=11、robRange(1,4)=10、answer=max(11,10)=11。 因为：时间 O(n) · 空间 O(1)。最优解一定不同时含首尾，于是把环拆成两条线性数组：A=nums[0..n-2]（去尾）、B=nums[1..n-1]（去首），各跑一遍 LC198 的 robRange，answer=max(robRange A, robRange B)；n==1 特判直接返回 nums[0]。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func rob(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
	if n == 2 {
		return max(nums[0], nums[1])
	}
	// 由于首尾是相邻的，所以需要对比 [0，n-1]、[1，n] 这两个区间的最大值
	return max(rob213_1(nums, 0, n-2), rob213_1(nums, 1, n-1))
}

func rob213_1(nums []int, start, end int) int {
	preMax := nums[start]
	curMax := max(preMax, nums[start+1])
	for i := start + 2; i <= end; i++ {
		tmp := curMax
		curMax = max(curMax, nums[i]+preMax)
		preMax = tmp
	}
	return curMax
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="house-robber", nums=[2,3,2]
    //    期望：nums=[2,7,9,3,1] 时 robRange(0,3)=11、robRange(1,4)=10、answer=max(11,10)=11。
    //
    // 2. 失败 / 未命中
    //    检查：只跑一趟 LC198 把整圈当线性会同时选中首尾，得到非法方案；忘了 n==1 特判会让 robRange(0,n-2) 退化成 robRange(0,-1)；误以为还要单独算“首尾都不偷”；A、B 区间写反。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC198 打家劫舍 (直线版)；LC337 打家劫舍 III (二叉树版)
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意房子围成一圈，第 0 间和最后一间也相邻。nums=[2,7,9,3,1] 答案 11；反例 nums=[2,3,2] 首尾两个 2 相邻不能同时偷，答案 3。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化最优解一定不同时含首尾，于是把环拆成两条线性数组：A=nums[0..n-2]（去尾）、B=nums[1..n-1]（去首），各跑一遍 LC198 的 robRange，answer=max(robRange A, robRange B)；n==1 特判直接返回 nums[0]。
4. 4证明首尾相邻 → 最优解最多含其一；去尾的方案全在 A、去首的方案全在 B，两类穷尽所有合法解；首尾都不偷的方案同属 A、B 已被自动覆盖；robRange 内每步 cur 恒为该线到当前房的最大收益。n 是房子数量。
5. 5复杂度时间 O(n)，空间 O(1)