class?Solution?{

public:

/*

????dp[i]:??考虑i个以内的房屋被偷窃的最大金额

????如果偷i号房间，那么金额就是nums[i]+dp[i-2]

????如果不偷i号房间，就可能偷i-1号房间，只是可能偷，那么金额是dp[i-1]

????nums?????1???2???3???1

????idnex????0???1???2???3

????dp???????1???2???4???3

????dp[i]=max(dp[i],nums[i]+dp[i-2])

????

*/

????int?rob(vector<int>&?nums)?{

????????int?m=nums.size();

????????if(m==0)?return?0;

????????if(m==1)?return?nums[0];

????????vector<int>dp(m);

????????dp[0]=nums[0];

????????dp[1]=max(nums[0],nums[1]);

????????for(int?i=2;i<=m-1;i++){

????????????dp[i]=max(dp[i-1],nums[i]+dp[i-2]);

????????}

????????return?dp[m-1];

????}

};

class?Solution?{

public:

/*

????dp[i]：i个房间内窃取的最大金额

????和上一题一样，取决第i个房间偷不偷，不同的地方是首尾房间相邻成环了，就首尾肯定不能一起偷，所以分两种情况：

????掐头和去尾，在这之两者中比较哪种情况窃取的金额会多些

????理解了上面的话，基本就和前一题差不多了，只不过要分两种情况计算

????偷第i个房间：nums[i]+dp[i-2]

????不偷第i个房间，可能偷第i-1个，dp[i-1]

????nums???1???2???3???????????nums????2???3???1

????index??0???1???2???????????index???1???2???3

????dp?????1???2???4???????????dp??????2???3???3

????dp=max(dp[i-1],nums[i]+dp[i-2])

*/

????int?help(vector<int>&nums,int?start,int?end){

????????if(start==end)?return?nums[start];

????????int?m=nums.size();

????????vector<int>dp(m);

????????dp[start]=nums[start];

????????dp[start+1]=max(nums[start],nums[start+1]);

????????for(int?i=start+2;i<=end;i++){

????????????dp[i]=max(dp[i-2]+nums[i],dp[i-1]);

????????}?

????????return?dp[end];

????}

????int?rob(vector<int>&?nums)?{

????????int?m=nums.size();

????????if(m==0)?return?0;

????????if(m==1)?return?nums[0];

????????int?res1=help(nums,0,m-2);

????????int?res2=help(nums,1,m-1);

???????

????????return?max(res1,res2);

????}

};