leetcode #213打家劫舍 II

题目描述

在上次盗窃完一条街道之后，窃贼又转到了一个新的地方，这样他就不会引起太多注意。这一次，这个地方的所有房屋都围成一圈。这意味着第一个房子是最后一个是紧挨着的。同时，这些房屋的安全系统与上次那条街道的安全系统保持一致。

给出一份代表每个房屋存放钱数的非负整数列表，确定你可以在不触动警报的情况下盗取的最高金额。

解题思路

首先，把这个环形的街道转化为直线，因为第一个房子和最后一个房子不能同时打劫，因此可以把这个环形街道分为两部分，第一间房子到第n-1间房子和第二间房子到第n间房子。
然后，考虑这个直线的房子，可以用动态规划解决，我们可以注意到，第i间房子对应的最大金额由第i-1间房子和第i-2间房子的最大金额决定，即money(i) = max(money(i-1),money(i-2)+nums[i])

代码

class Solution(object):
    def rob(self, nums):
        n = len(nums)
        if n==0:
            return 0
        elif n==1:
            return nums[0]
        sum1 = single_rob(0,n-1,nums)
        sum2 = single_rob(1,n,nums)
        return max(sum1,sum2)

def single_rob(first,last,nums):
    pre = 0
    ppre = 0
    for i in range(first,last):
        if ppre+nums[i] >= pre:
            ppre,pre = pre, ppre+nums[i]
        else:
            ppre = pre
    return pre