题目描述
房子围成环，首尾相邻、不能同偷相邻两家，求最多偷多少。
思路解析
转折点：环的麻烦只在「首尾相邻」这一处。只要强行让首尾有一个不偷，环就断成了直线。于是分两种：① 偷范围 [0…n−2]（放弃最后一家）；② 偷范围 [1…n−1]（放弃第一家）。两种都用打家劫舍 I 的直线 DP，取较大者。直线 DP 的递推是 cur = max(prev1, prev2 + x)：要么不偷这家(沿用 prev1)，要么偷它(prev2 + 这家钱)。
情况① · 放弃最后一家：情况①：把最后一家（下标 3）划掉（灰），只在前三家里偷。滚动变量 prev2=0、prev1=0。逐家推一遍。
①第 0 家 · 钱=1：第 0 家：不偷=0，偷它=prev2+1=1。取大得 1。滚动更新 prev2=0、prev1=1。
①第 1 家 · 钱=2：第 1 家：不偷=prev1=1，偷它=prev2+2=0+2=2（偷它就不能偷相邻的第 0 家）。取大得 2。更新 prev2=1、prev1=2。
①第 2 家 · 钱=3 → 情况①=4：第 2 家：不偷=2，偷它=prev2+3=1+3=4。取大得 4——正是偷第 0、2 家（1+3）。情况① 答案 = 4。
情况② · 放弃第一家：情况②：换成把第一家（下标 0）划掉（灰），只在后三家里偷。滚动变量清零，重跑一遍。
②第 1 家 · 钱=2：从第 1 家起：偷它=2 比不偷=0 好，得 2。更新 prev2=0、prev1=2。
②第 2 家 · 钱=3：第 2 家：偷它=prev2+3=0+3=3，比留着第 1 家的 2 更划算。得 3。更新 prev2=2、prev1=3。
②第 3 家 · 钱=1 → 情况②=3：第 3 家：偷它=prev2+1=2+1=3，和不偷的 3 打平——偷它并不更好。情况② 答案 = 3（就守住偷第 2 家的 3）。
两种情况取较大：两种情况取大：max(4, 3) = 4，对应偷第 0、2 家。这就是环形版的答案——拆环带来的额外代价，只是把直线 DP 跑了两遍。
直线版 rob：prev2、prev1 滚动，cur = max(prev1, prev2 + x)。环形版只是把它调用两次、传不同区间，再取最大。
处理环形约束的常用招：枚举「断开点 / 哪个端点不选」，把环拆成几个线性问题分别解、再合并。环形子数组最大和也用这招。
参考代码（Python）
1def rob_line(arr): # 打家劫舍 I 的直线版
2 prev2, prev1 = 0, 0
3 for x in arr:
4 prev2, prev1 = prev1, max(prev1, prev2 + x)
5 return prev1
6if len(nums) == 1: return nums[0]
7return max(rob_line(nums[:-1]), # 去掉最后一家
8 rob_line(nums[1:])) # 去掉第一家复杂度分析
- 时间复杂度：O(n) —— 两遍线性扫描
- 空间复杂度：O(1) —— 滚动变量
套路模板
记住骨架：先解线性、再对「环的接缝」分情况各跑一次取最优。关键是想清楚「哪两个因为成环而互斥」。
1# 环形 = 固定某端点的取舍，拆成线性各算一次
2def solve_line(arr): ... # 先写好线性版
3ans = max(solve_line(去掉首), # 情况A
4 solve_line(去掉尾)) # 情况B易错点
- 错误写法：直接对整个环跑直线 DP → 正确写法：必须拆成去头/去尾两次（否则可能同时偷了首尾两家(它们相邻)）
- 错误写法：只有一家时也去拆 → 正确写法：n==1 单独返回 nums[0]（去头去尾会得到空数组）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。