难度: Medium
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 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 = [1,2,3] 输出：3
提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000运行时间: 12 ms
内存: 16.0 MB
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)==1:
return nums[0]
if len(nums)==2 or len(nums)==3:
return max(nums)
value = 0
# case 1 : cheat first house
dp1 = [nums[0]] * (len(nums)-1)
for i in range(2, len(nums)-1):
dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])
val1 = max(dp1)
# case 2 : not cheat first house
dp2 = [0] * (len(nums))
for i in range(1, len(nums)):
dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i])
val2 = max(dp2)
return max(val1, val2)
这道题是经典的动态规划问题。由于房屋围成一圈，意味着第一个房屋和最后一个房屋不能同时偷窃。因此可以将问题分为两种情况：偷窃第一个房屋和不偷窃第一个房屋。对于每种情况，可以使用一维动态规划数组分别求解。最终的结果就是两种情况下的最大值。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums)==1:
return nums[0]
if len(nums)==2 or len(nums)==3:
return max(nums)
# case 1 : cheat first house
dp1 = [nums[0]] * (len(nums)-1)
for i in range(2, len(nums)-1):
# 对于第 i 个房屋，可以选择偷或不偷
# 如果偷，则最大金额为前 i-2 个房屋的最大金额加上当前房屋的金额
# 如果不偷，则最大金额为前 i-1 个房屋的最大金额
dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])
val1 = max(dp1)
# case 2 : not cheat first house
dp2 = [0] * (len(nums))
for i in range(1, len(nums)):
# 与 case 1 类似，但起始索引为 1
dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i])
val2 = max(dp2)
return max(val1, val2)
在代码中，通过单独处理nums长度为1、2或3的情况，确保了不会访问动态规划数组dp1和dp2的非法索引。当数组长度为1时，直接返回该元素值；当长度为2或3时，直接返回数组中的最大值。这样的处理避免了对动态规划数组进行越界访问，因为在这些特殊情况下，不需要执行后续的动态规划逻辑。
dp1数组的初始值设为nums[0]是因为在第一种情况中我们假设第一个房屋被偷窃，因此起始金额为第一个房屋的金额。对于dp2数组，初始值设为0是因为在第二种情况中我们不偷第一个房屋，因此起始金额为0。这种初始值设定是为了正确地反映两种情况下的偷窃起点和相应的累积金额。
dp1数组的更新从索引2开始，因为在偷第一个房屋的情况下，第二个房屋（索引1）不能被偷，因此动态规划从第三个房屋（索引2）开始。而dp2数组从索引1开始更新，因为我们没有偷第一个房屋，所以从第二个房屋（索引1）开始偷窃是可能的。这种区别是因为两种情况下的起始偷窃房屋不同。
是的，这两种情况完全覆盖了所有可能的偷窃组合。由于房屋是环状排列，选择偷窃第一家或不偷窃第一家将影响最后一家是否可偷。将问题分解为这两种情况可以独立地计算每种情况的最大偷窃金额，然后从中选择最大值，确保考虑了所有的偷窃组合。