题目
BM79 打家劫舍(二)
描述
你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
分析
跟【动态规划-BM78 打家劫舍(一)】的区别是最后一家与第一家相连成环。
这时，第一家与最后一定有一个是一定不取的，分两种情况讨论。
当取第一家时，只需在原有基础上，不要遍历到最后一家即可，ans=dp[n-1]
当不取第一家时，dp[1] = 0, 遍历到最后一家，ans = dp[n]
取两种情况的最大值。
代码
class Solution:
def rob(self , nums: List[int]) -> int:
# write code here
n = len(nums)
dp = [0]*(n+1)
# 取第一家
dp[1] = nums[0]
# 最后一家不管，不遍历
for i in range(2,n):
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
# 取到最后一家的前一家
ans1 = dp[n-1]
# 不取第一家
dp = [0]*(n+1)
# 遍历到最后一家
for i in range(2,n+1):
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
# 取到最后一家
ans2 = dp[n]
return max(ans1,ans2)
