213、打家劫舍 II

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

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

示例 1:

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

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

这道题一开始卡了很久，之后看了看别人的题解，才理解。
这道题的关键就是围成一圈，第一个房屋和最后一个房屋是挨着的，让原本不复杂的题目变得复杂了起来。
数组长度为n
那我们可以做一个分类讨论，如果选择了第n个房屋，那第1个和第n-1个房屋是无法选择的。nums[1:n-2]+nums[n-1]
而如果不选择第n个房屋，那么就是考虑第一个到第n-1个房屋 nums[:n-1]
两种情况求最大值即可。

这样的话只要这么做，就不用再去考虑第一个和最后一个挨着这件事了，把问题变成了如何解决一个单排的打家劫舍问题，这个问题就简单多了，用简单的动态规划就能解决了。
状态转移方程就是dp[n]=max(dp[n-1],dp[n-2]+nums[n])
很简单，这里就不做推导了。
总结一下：我们想要求围绕的问题，是很复杂的，我们不妨通过分类讨论将其简化，将它变成一个简单的单排问题，减少难度，这是需要去借鉴学习的。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        int money1=robfun(nums,0,n-1);
        int money2=robfun(nums,1,n-2)+nums[n-1];
        return money1>money2?money1:money2;
    }

    int robfun(vector<int>& nums,int start,int end){
        int size=end-start;
        if(size<=0) return 0;
        if(size==1) return nums[start];
        int dp[size];
        for(int i=0;i<size;i++) dp[i]=0;
        dp[0]=nums[start];
        dp[1]=nums[start]>nums[start+1]?nums[start]:nums[start+1];
        for(int i=2;i<size;i++){
            dp[i]=(dp[i-2]+nums[i+start])>dp[i-1]?(dp[i-2]+nums[i+start]):dp[i-1];
        }
        return dp[size-1];
    }
};