题目描述
房子围成环，首尾相邻、不能同偷相邻两家，求最多偷多少。
nums = [1, 2, 3, 1]
输出 = 4 （偷第 1、3 家 = 1 + 3）
思路解析
环的麻烦只在「首尾相邻」。那就分两种：① 偷范围 [0 … n−2]（放弃最后一家）；② 偷范围 [1 … n−1]（放弃第一家）。两种都用打家劫舍 I 的直线 DP，取较大的那个。
情况① 去掉最后一家：放弃最后一家（灰色），对 [1, 2, 3] 跑直线版：dp 得到 4（偷第 1、3 家 = 1+3）。
情况② 去掉第一家：放弃第一家（灰色），对 [2, 3, 1] 跑直线版：最优是偷 3，得 3。
取较大：两种情况取大：max(4, 3) = 4，就是环形版的答案。
直线版 rob：prev2、prev1 滚动，cur = max(prev1, prev2 + x)。环形版只是把它调用两次、传不同区间，再取最大。
处理环形约束的常用招：枚举「断开点 / 哪个端点不选」，把环拆成几个线性问题分别解、再合并。环形子数组最大和也用这招。
参考代码（Python）
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) —— 滚动变量
套路模板
记住骨架：先解线性、再对「环的接缝」分情况各跑一次取最优。关键是想清楚「哪两个因为成环而互斥」。
Python
1# 环形 = 固定某端点的取舍，拆成线性各算一次
2def solve_line(arr): ... # 先写好线性版
3ans = max(solve_line(去掉首), # 情况A
4 solve_line(去掉尾)) # 情况B易错点
- ❌ 直接对整个环跑直线 DP → ✅ 必须拆成去头/去尾两次（否则可能同时偷了首尾两家(它们相邻)）
- ❌ 只有一家时也去拆 → ✅ n==1 单独返回 nums[0]（去头去尾会得到空数组）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。