LeetCode213.House-Robber-II＜打家劫舍II＞

题目：

 

思路：

在版本一中增加了一个条件 那就是首尾相关联。那么只需要进行两次循环即可。

第一次是循环是偷第一家的 那么循环到n-1 截至 并且保存一个cmp

第二次循环是不偷第一家的 循环到n截至。然后比较cmp 与 dp [n] 的最大值即可。

 

代码是：

//codeclass Solution {
public:int rob(vector<int>& nums) {int n = nums.size()-1;if(n==1) return max(nums[0],nums[1]);if(n==0) return nums[0];int dp[1000]={0};dp[0]=nums[0];dp[1]=max(dp[0],nums[1]);for(int i=2;i<n;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}int cmp = dp[n-1];dp[0]=0;dp[1]=nums[1];for(int i=2;i<=n;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}return max(cmp,dp[n]);}
};