90. 打家劫舍II （房子围成一圈）
题目
题解
class Solution:
def rob(self, nums: List[int]) -> int:
def dp(nums: List[int]) -> int:
N = len(nums)
# 定义状态：dp[i]表示从第i个房屋开始偷窃，能够偷到的最高金额
dp = [0 for i in range(N)]
for i in range(N-1, -1, -1):
if i == N-1:
dp[i] = nums[i]
elif i == N-2:
dp[i] = max(nums[i], nums[i+1])
else:
dp[i] = max(dp[i+1], nums[i] + dp[i+2])
return dp[0]
if len(nums) == 1:
return nums[0]
res = max(dp(nums[:-1]), dp(nums[1:]))
return res