## 题目描述：

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

## Python代码：

``````class Solution:
# @param {integer[]} nums
# @return {integer}
def rob(self, nums):
if len(nums) == 1:
return nums[0]
return max(self.robLinear(nums[1:]), self.robLinear(nums[:-1]))

# @param num, a list of integer
# @return an integer
def robLinear(self, num):
size = len(num)
odd, even = 0, 0
for i in range(size):
if i % 2:
odd = max(odd + num[i], even)
else:
even = max(even + num[i], odd)
return max(odd, even)
``````

``````class Solution:
def rob(self, nums):
def rob(nums):
now = prev = 0
for n in nums:
now, prev = max(now, prev + n), now
return now
return max(rob(nums[len(nums) != 1:]), rob(nums[:-1]))
``````

Pingbacks已关闭。

1. liwzhi 发布于 2015年10月12日 12:58 #

class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return 0

if len(nums)<=3:
return max(nums)

dp = [0 for i in range(len(nums))]
dp[0] = nums[0]
dp[1] = nums[1]
dp[2] = max(nums[1],nums[2])
for i in range(3,len(nums)):
dp[i] = max(dp[i-1],nums[i] + max(dp[1:i-1]))
maxValue1 = dp[len(nums)-1]

dp = [0 for i in range(len(nums))]
dp[0] = nums[0]
dp[1] = nums[1]
for i in range(2,len(nums)-1):
dp[i] = max(dp[i-1],nums[i] + max(dp[:i-1]))
maxValue2 = dp[len(nums)-2]
return max(maxValue1,maxValue2)