原題
在上次打劫完一條街道之后骨宠，竊賊又發(fā)現(xiàn)了一個(gè)新的可以打劫的地方赶袄，但這次所有的房子圍成了一個(gè)圈经柴，這就意味著第一間房子和最后一間房子是挨著的挟憔。每個(gè)房子都存放著特定金額的錢(qián)钟些。你面臨的唯一約束條件是：相鄰的房子裝著相互聯(lián)系的防盜系統(tǒng)，且 當(dāng)相鄰的兩個(gè)房子同一天被打劫時(shí)绊谭，該系統(tǒng)會(huì)自動(dòng)報(bào)警政恍。
給定一個(gè)非負(fù)整數(shù)列表，表示每個(gè)房子中存放的錢(qián)达传， 算一算篙耗，如果今晚去打劫迫筑，你最多可以得到多少錢(qián) 在不觸動(dòng)報(bào)警裝置的情況下。
樣例
給出nums = [3,6,4], 返回 6宗弯， 你不能打劫3和4所在的房間脯燃，因?yàn)樗鼈儑梢粋€(gè)圈，是相鄰的．
解題思路
- 狀態(tài)轉(zhuǎn)移方程和【House Robber I】是一樣的蒙保，唯一的區(qū)別是房子看成環(huán)狀的辕棚，所以首位只能二選一
- 不包括頭求一個(gè)最大值，不包括尾再求一個(gè)最大值邓厕。最后返回較大的
完整代碼
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0 for i in range(len(nums))]
dp[0], dp[1] = 0, nums[1]
for i in range(2, len(nums)):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
ans = dp[len(nums) - 1]
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return max(dp[len(nums) - 2], ans)
