213. 打家劫舍 II - House Robber II

🎯 问题描述（来源于LeetCode）

描述：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈，这意味着第一间房屋和最后一间房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums，请计算 在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

说明：

环形：第一间和最后一间不能同时偷。
数组长度至少为 1。

示例：

示例 1：

1
2
3

输入: nums = [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额=2），然后偷窃 3 号房屋（金额=2），因为他们是相邻的。所以最优是偷 2 号房屋 (金额=3)。

示例 2：

1
2
3

输入: nums = [1,2,3,1]
输出: 4
解释: 偷 1 号 (1) 和 3 号 (3) 得到 4；或者偷 2 号 (2) 和 4 号 (1) 得到 3。最大值是 4。

💻 解题思路

思路：环形问题拆解为两个线性问题

算法步骤

定义辅助函数 rob1(nums) 用于解决线性（非环形）情况，返回最大金额。其内部使用动态规划（滚动变量）：
- f0, f1 = 0, 0 分别表示不偷当前房和偷当前房的最大值。
- 遍历每个金额 x，更新 f0, f1 = f1, max(f1, f0 + x)。
- 最终 f1 即为线性情况的最大值。
对于环形情况，分为两种情况：
- 偷第一间房屋：则不能偷最后一间，因此考虑 nums[0] + rob1(nums[2:-1])（去掉第一间和最后一间，并加上第一间）。
- 不偷第一间房屋：则最后一间可偷可不偷，因此考虑 rob1(nums[1:])（去掉第一间）。
取两种情况的最大值作为答案。
注意：如果数组长度为 1，直接返回 nums[0]（本解法中 nums[1:] 为空，rob1 返回 0，但 nums[0]+rob1(nums[2:-1]) 中 nums[2:-1] 可能越界，需要特殊处理。实际代码中 nums[2:-1] 在长度小于3时会得到空列表，rob1 返回0，结果正确；但 nums[1:] 也会正确。不过更严谨的做法是处理单元素情况，但用户代码未显式处理，在 Python 中 nums[2:-1] 当 len(nums)=1 时，2:-1 会得到空列表，无错误。）

代码实现

from typing import List

class Solution:
    def rob1(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for x in nums:
            f0, f1 = f1, max(f1, f0 + x)
        return f1

    def rob(self, nums: List[int]) -> int:
        # 处理环形：要么不偷第一间，要么不偷最后一间
        return max(nums[0] + self.rob1(nums[2:-1]), self.rob1(nums[1:]))

📊 性能分析

时间复杂度： $O(n)$ ，每个子数组遍历一次。
空间复杂度： $O(1)$ ，仅使用常数个变量。

思考

该解法巧妙地利用线性打家劫舍的滚动变量版本，将环形问题分解为两个互斥的线性子问题。代码简洁高效，无需额外数组。注意边界：当 nums 长度小于 3 时，nums[2:-1] 会得到空列表，rob1([]) 返回 0，结果正确。但如果是长度为 1 的情况，max 中第一项为 nums[0]+0，第二项为 rob1(nums[1:]) 即 rob1([])=0，最终返回 nums[0]，正确。因此无需额外判断。此解法是 LeetCode 213 的推荐解法之一。