打家劫舍 II

转折点：环的麻烦只在「首尾相邻」这一处。只要强行让首尾有一个不偷，环就断成了直线。于是分两种：① 偷范围 [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)。环形版只是把它调用两次、传不同区间，再取最大。

处理环形约束的常用招：枚举「断开点 / 哪个端点不选」，把环拆成几个线性问题分别解、再合并。环形子数组最大和也用这招。

边界三连：三种边界先想清。

面试官常追问：三个高频追问。