213. 打家劫舍 II

 1 class Solution 
 2 {
 3 public:
 4     int rob(vector<int>& nums) 
 5     {
 6         int n = nums.size();
 7         if(n == 0) return 0;
 8         else if(n == 1) return nums[0];
 9         else if(n == 2) return max(nums[0], nums[1]);
10         else if(n == 3) return max(max(nums[1], nums[0]), nums[2]);
11 
12         //最后一家不偷
13         vector<int>dp1(n - 1, 0);
14         dp1[0] = nums[0];
15         dp1[1] = max(nums[1], nums[0]);
16         for(int i = 2; i < n - 1; ++ i)dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
17         
18         //第一家不偷
19         vector<int>dp2(n, 0);
20         dp2[1] = nums[1];
21         dp2[2] = max(nums[2], nums[1]);
22         for(int i = 3; i < n; ++ i)dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);
23 
24         return max(dp1.back(), dp2.back());
25     }
26 };