打家劫舍 II 的环形房屋如何拆成两个线性 DP？

简化版

打家劫舍 II 比 I 多了首尾相邻限制。环形数组中第一间和最后一间不能同时偷，所以拆成两个线性问题：偷 [0..n-2] 或偷 [1..n-1]，答案取两者最大。

详细版

线性打家劫舍的状态是：到当前房屋为止，最大收益为 max(prev2 + nums[i], prev1)。环形问题的关键是首尾互斥，如果偷第一间就不能偷最后一间，如果偷最后一间就不能偷第一间。

因此可以排除最后一间跑一次线性 DP，再排除第一间跑一次线性 DP。特殊情况 n=1 直接返回 nums[0]。时间复杂度 O(n)，空间复杂度 O(1)。

完整版教学

一、环形限制改变了什么

线性版本中，只有相邻房屋不能同时偷；环形版本里，nums[0] 和 nums[n-1] 也相邻。

线性：0 - 1 - 2 - 3
环形：0 - 1 - 2 - 3
      └─────────┘

这个额外边会让普通线性 DP 可能选出非法答案。例如 [2,3,2]，线性可能选 2 + 2 = 4，但首尾不能同时偷，正确答案是 3。

二、为什么可以拆成两个线性区间

首尾不能同时选，合法方案必然属于下面两类之一：

情况	可考虑区间
不偷最后一间	`[0..n-2]`
不偷第一间	`[1..n-1]`

所有合法方案至少满足其中一个条件。即使某个方案首尾都不偷，它也会同时被两个区间覆盖，取最大不会漏答案。

记忆钩子：环形打家劫舍不是重新发明状态，而是切断首尾边。

三、线性子问题如何求

线性打家劫舍的转移是：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

含义是第 i 间房有两种选择：不偷它，收益沿用 dp[i-1]；偷它，就不能偷 i-1，收益是 dp[i-2] + nums[i]。

四、状态压缩写法

因为当前状态只依赖前一项和前两项，可以用两个变量：

prev2：处理到 i-2 的最大收益
prev1：处理到 i-1 的最大收益
cur = max(prev1, prev2 + nums[i])

这个 helper 可以复用两次，分别处理两个区间。

五、代码模板

int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

int robRange(int[] nums, int l, int r) {
    int prev2 = 0;
    int prev1 = 0;
    for (int i = l; i <= r; i++) {
        int cur = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

注意 n=1 必须单独处理，否则两个区间会变成空或非法。

六、用样例验证拆分

以 [1,2,3,1] 为例：

区间	线性答案	说明
`[0..2]` 即 `[1,2,3]`	4	偷 1 和 3
`[1..3]` 即 `[2,3,1]`	3	偷 3

最终答案是 4。这个方案没有偷最后一间，所以合法。

七、常见误区与追问

误区：直接套线性打家劫舍。 会可能同时选择首尾房屋，违反环形相邻限制。
误区：只讨论偷第一间和偷最后一间。 更好写法是排除最后或排除第一，覆盖所有合法方案。
误区：忘记处理 n=1。 单个房屋既是首也是尾，但没有另一间相邻房，答案就是它本身。
追问：首尾都不偷的方案会不会漏？ 不会，它同时包含在两个线性区间中。
追问：复杂度是多少？ 两次线性 DP，时间 O(n)，空间 O(1)。
追问：如果是二叉树房屋呢？ 那是打家劫舍 III，需要树形 DP，状态是偷或不偷当前节点。

八、加强记忆

打家劫舍 II 的关键动作是“把环切成两条线”。首尾相邻导致二者不能同时选，所以答案一定能在“不要最后一间”和“不要第一间”两个线性问题中找到。线性 helper 仍然是 max(偷当前, 不偷当前)，只不过要跑两次。记住 [2,3,2] 这个反例，就不会误把环形题直接写成线性题。

简化版

详细版