题目描述：

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.

题目大意：

注意：这道题是题目House Robber（入室盗贼）的扩展。

抢完上一条街的房屋之后，小偷又给自己找了一个不太引人注意的新作案场所。这一次，所有的房屋围成一个环形。也就是说第一个房屋和最后一个房屋相邻。与此同时，这些房屋的安保系统与上一条街的相同。

给定一组非负整数代表每一件房屋的金钱数，求解在不惊动警察的情况下一晚上最多可以抢到的钱数。

解题思路：

讨论是否抢劫第一件房屋。如果是，则不可以抢最后一件房屋。否则，可以抢最后一间房屋。

以此为依据，将环形DP问题转化为两趟线性DP问题，可以复用House Robber的代码。

另外需要特判一下只有一件房屋的情形。

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)

另附一个非常简洁的答案（https://leetcode.com/discuss/36586/6-lines-function-body）：

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]))

 

本文链接：http://bookshadow.com/weblog/2015/05/20/leetcode-house-robber-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码