第九周作业——高级编程技术

#213

题目来源：https://leetcode.com/problems/house-robber-ii/description/

题目分析：这是house-robber的延伸，在上次盗窃完一条街道之后，窃贼又转到了一个新的地方，这个地方的所有房屋都围成一圈。这意味着第一个房子是最后一个是紧挨着的。当然这些房屋的安全系统与上次那条街道的安全系统保持一致。现在给出一份代表每个房屋存放钱数的非负整数列表，确定你可以在不触动警报的情况下盗取的最高金额。

题目思路：这是第一版的延伸，问题就是这些房屋构成了一个环状，而不是线状排列。只需考虑下面两种情况： 起点元素作为了加数，终点元素一定就不能作为加数，最大权值和应该等于之前所定义的most[len - 1] ；起点元素没有作为加数，则假设去掉这个元素，起点顺移一位，终点元素是否作为加数交由算法自行决定。

代码如下：

class Solution(object):

    def rob(self, nums):

        if len(nums) == 0: return 0

        if len(nums) == 1: return nums[0]

        if len(nums) == 2:  

         if nums[0] > nums[1]:

         return nums[0]

         else:

         return nums[1]

        return max(self.robber(nums[0:-1]), self.robber(nums[1:]))

    def robber(self, nums):

        if len(nums) == 1: return nums[0]

        m1 = nums[0]

        if nums[1] > nums[0]:

         m2 = nums[1]

        else:

         m2 = nums[0]

        if len(nums) == 2: return m2

        for i in range(2, len(nums)):

            m3 = max(m2, m1+nums[i])

            m1 = m2

            m2 = m3

        return m3