leetcode--213--打家劫舍 II

题目：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

链接：https://leetcode-cn.com/problems/house-robber-ii

思路：
1、环形打家劫舍相当于找[0:n-1]、[1:n]房屋劫舍的最大值
2、对于对列式打家劫舍，采用动态规划的解法，转移方程 dp[n] = max(dp[n-2]+nums[n], dp[n-1])

Python代码:

class Solution(object):

    def sub_rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = []
        if len(nums)==0:
            return 0
        elif len(nums)==1:
            return nums[0]
        elif len(nums)==2:
            return max(nums)
        
        dp.append(nums[0])
        dp.append(max(nums[:2]))

        for i in range(2, len(nums)):
            mmax = max(dp[i-2]+nums[i], dp[i-1])
            dp.append(mmax)
        return dp[-1]
        

    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 环形打家劫舍相当于 找[0:n-1]、[1:n]房屋劫舍的最大值
        size = len(nums)
        if size==0:
            return 0
        elif size==1:
            return nums[0]
        elif size==2:
            return max(nums)
        
        return max(self.sub_rob(nums[:size-1]), self.sub_rob(nums[1:size]))

C++代码：

class Solution {
public:
    int sub_rob(vector<int>& ls){
        int size=ls.size();
        if (size==0) return 0;
        if (size==1) return ls[0];
        if (size==2) return max(ls[0],ls[1]);

        vector<int> dp;
        dp.push_back(ls[0]);
        dp.push_back(max(ls[0], ls[1]));
        for (int i=2; i<size; i++){
            int mmax = max(dp[i-2]+ls[i], dp[i-1]);
            dp.push_back(mmax);
        }
        return dp[dp.size()-1];
    }

    int rob(vector<int>& nums) {
        int size = nums.size();
        if (size==0) return 0;
        if (size==1) return nums[0];
        if (size==2) return max(nums[0], nums[1]);

        vector<int> nums_a(nums.begin(), nums.begin()+size-1);
        vector<int> nums_b(nums.begin()+1, nums.begin()+size);
        return max(sub_rob(nums_a), sub_rob(nums_b));
    }
};