题意：
        给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，你不能偷相邻的两家，并且第一个房间和最后一个房间视为相邻。
        请你计算在不被发现的前提下最多的偷窃金额。


方法一：
动态规划

思路：
        dp[ i ]表示前i个房间最多的偷窃金额。
        

        因为第一个房间和最后一个房间视为相邻，所以可以划分为两个区间【1：n-1】和【2:n】。
       最后取两者的最大值。
    
        



class Solution {
public:
    int dp1[200005]={0};//dp[i]表示前i个房间最多的偷窃金额
    int dp2[200005]={0};
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1)
            return nums[0];
        dp1[1]=nums[0];//初始化
        for(int i=2;i<=n-1;i++){//区间[1:n-1]
            dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i-1]);//状态转移方程
        }
        for(int i=2;i<=n;i++){//区间[2:n]
            dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i-1]);//状态转移方程
        }
        return max(dp1[n-1],dp2[n]);
    }
};


时间复杂度：
空间复杂度：

方法二：
滚动数组优化

思路：
        根据转移转移方程，可知当前项只与前两项有关。
        因此可以不用一维数组，改用几个变量实现。（滚动数组）

 


class Solution {
public:
    
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1)
            return nums[0];
        if(n==2)
            return max(nums[0],nums[1]);
        int t1=nums[0],t2=max(nums[0],nums[1]);//初始化
        for(int i=2;i<=n-2;i++){//区间[0:n-2]
            int t=max(t1+nums[i],t2);//状态转移方程
            t1=t2;
            t2=t;
        }
        int t3=nums[1],t4=max(nums[1],nums[2]);//初始化
        for(int i=3;i<=n-1;i++){//区间[1:n-1]
            int t=max(t3+nums[i],t4);//状态转移方程
            t3=t4;
            t4=t;
        }
        return max(t2,t4);
    }
};

时间复杂度：
空间复杂度：