题目描述

注意事项: 这是打家劫舍的延伸。

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

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

我的解法——DP（AC）

因为第一个element 和最后一个element不能同时出现. 则分两次call House Robber I. case 1: 不包括最后一个element. case 2: 不包括第一个element.
dp[i]表示前i个房子所能抢的最多金额。
复杂度O(n)
Beat 85.71%

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        res_not_begin = [0] * length
        res_begin = [0] * length
        if(length >= 1):
            res_begin[0] = nums[0]
            res_not_begin[0] = 0
        else:
            return 0
        if(length >= 2):
            res_begin[1] = nums[0]
            res_not_begin[1] = nums[1]
        
        for i in range(2,length - 1):
            if(res_begin[i - 1] >= res_begin[i - 2] + nums[i]):
                res_begin[i] = res_begin[i - 1]
            else:
                res_begin[i] = res_begin[i - 2] + nums[i]
            
            if(res_not_begin[i - 1] >= res_not_begin[i - 2] + nums[i]):
                res_not_begin[i] = res_not_begin[i - 1]
            else:
                res_not_begin[i] = res_not_begin[i - 2] + nums[i]
        
        if(length >= 3):
            if(res_not_begin[length - 2] >= res_not_begin[length - 3] + nums[length - 1]):
                res_not_begin[length - 1] = res_not_begin[length - 2]
            else:
                res_not_begin[length - 1] = res_not_begin[length - 3] + nums[length - 1]

            res_begin[length - 1] = res_begin[length - 2]
            
        return max(res_not_begin[length - 1],res_begin[length - 1])

最优解法——DP

在做这题时发现House Robber I中的代码还可以进一步的优化，可以将数组也省略掉而只使用两个变量来存储值，这样空间复杂度也降到了O(1)。代码更优了。

class Solution {  
public:  
    int rob(vector<int>& nums) {  
        int length=nums.size();  
        if(length==0)  
            return 0;  
        if(length==1)  
            return nums[0];  
              
        return max(robDiv(nums,0,length-2),robDiv(nums,1,length-1));  
    }  
      
    int robDiv(vector<int> &nums,int first,int last)  
    {  
        //因为只需要比较第A[i-2]+nums[i]和A[i-1]的大小，所以可以把House Robber I中的数组也省略掉，  
        //而只需要两个变量来存储着两个值，这样更能节约空间。  
        //这里pLast存储的是House Robber I中A[i-1]的值，  
        //ppLast存储的是House Robber I中A[i-2]的值，逻辑和House Robber I是一样的。  
        int pLast=0,ppLast=0;  
        for(int i=first;i<=last;i++)  
        {  
            int tmp=pLast;  
            pLast=max(ppLast+nums[i],pLast);  
            ppLast=tmp;  
        }  
        return pLast;  
    }  
};  