打家劫舍 II

难度: Medium

一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

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

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [0]
输出：0

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

注意：本题与主站 213 题相同： https://leetcode-cn.com/problems/house-robber-ii/

Submission

运行时间: 20 ms

内存: 16.1 MB

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
    
        def rob(nums):
            cur, pre = 0, 0
            for num in nums:
                cur, pre = max(pre + num, cur), cur 
            return cur 
        
        first_max = rob(nums[1:])
        second_max = rob(nums[:-1])
        return max(first_max, second_max)

Explain

此问题是经典的打家劫舍问题的变种，其中房屋是环形排列的。由于第一个和最后一个房屋相邻，不能同时偷窃，因此问题可以分解为两个子问题：1）偷窃第一间到倒数第二间房屋的最大金额；2）偷窃第二间到最后一间房屋的最大金额。通过解决这两个子问题，取二者的最大值即可得到整个问题的解。内部函数rob处理的是标准的线性房屋排列的打家劫舍问题，使用动态规划的思想，其中cur表示当前房屋的最大偷窃金额，pre表示前一间房屋的最大偷窃金额。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0  # 如果没有房屋，返回0
        if n == 1: return nums[0]  # 如果只有一间房屋，返回该房屋金额
    
        def rob(nums):
            cur, pre = 0, 0  # 初始化当前和前一房屋的最大偷窃金额
            for num in nums:
                cur, pre = max(pre + num, cur), cur  # 更新当前房屋的最大偷窃金额
            return cur  # 返回最大偷窃金额
        
        first_max = rob(nums[1:])  # 计算偷窃第一间到倒数第二间房屋的最大金额
        second_max = rob(nums[:-1])  # 计算偷窃第二间到最后一间房屋的最大金额
        return max(first_max, second_max)  # 返回两种方案的最大金额

Explore

分解成两个子问题的方法在大多数情况下是有效的，因为这种方法确保了我们没有同时偷窃第一个和最后一个相邻的房屋。然而，需要注意的是，如果房屋数量非常少，比如只有两间房屋，这种分解就会导致某个子问题中没有房屋可偷（例如偷第二间到最后一间，但实际上只有两间房屋，第一间和第二间是同一间）。因此，当房屋数量少于三间时，这种分解需要特别的处理逻辑。

在动态规划的方法中，`cur`表示当前考虑的房屋能够提供的最大偷窃金额，而`pre`表示前一间房屋能提供的最大偷窃金额。状态转移方程`cur, pre = max(pre + num, cur), cur`的逻辑是：对于当前房屋，我们有两种选择，一是偷窃当前房屋加上前一个房屋留下的最大金额（`pre + num`），二是不偷当前房屋保持当前的最大金额（`cur`）。我们选择这两者之间的最大值作为新的`cur`。然后原始的`cur`值变成新的`pre`值，为下一轮迭代做准备。这确保了我们在遍历房屋时始终保持最大偷窃金额的更新。

对于只有两间房屋的情况，按照给定的解法，将分成两个子问题：1) 偷第一间到倒数第二间（即只偷第一间），2) 偷第二间到最后一间（即只偷第二间）。由于房屋数量只有两间，这两个子问题都只包含一间房屋，因此解决这两个子问题并取最大值的方法是正确的。可以通过直接比较两间房屋的金额来验证这一点，即直接返回`max(nums[0], nums[1])`。这种方法在只有两间房屋的情况下能够正确地给出最大的偷窃金额。