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

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

示例 1：

  1. Input: nums = [2,3,2]
  2. Output: 3
  3. Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

示例 2：

  1. Input: nums = [1,2,3,1]
  2. Output: 4
  3. Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
  4. Total amount you can rob = 1 + 3 = 4.

示例 3：

  1. Input: nums = [0]
  2. Output: 0

提示：

  • 1 ≤ nums.length ≤ 100
  • 0 ≤ nums[i] ≤ 1000

思路

在打家劫舍1的基础上，分类讨论两种情况：

  • 不偷第0家的方案；
  • 不偷最后一家的方案；
  • 两个方案里选一个价值最大的

代码

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         if( nums.size() == 0 )   return 0;
  5.         if( nums.size() == 1 )   return nums[0];
  6.         if( nums.size() == 2 )   return nums[0] > nums[1] ? nums[0] : nums[1];
  8.         int* dp_no_first = new int[ nums.size() ];
  9.         dp_no_first[0] = 0;
  10.         dp_no_first[1] = nums[1];
  11.         dp_no_first[2] = nums[1] > nums[2] ? nums[1] : nums[2];
  12.         for(int i = 3; i < nums.size(); i++) {
  13.             int take_it = nums[i] + dp_no_first[i-2];
  14.             int no_take = dp_no_first[i-1];
  15.             dp_no_first[i] = take_it > no_take ? take_it : no_take;
  16.         }
  17.         int max_no_first = *max_element(dp_no_first, dp_no_first + nums.size());
  19.         int* dp_no_last = new int[ nums.size() ];
  20.         dp_no_last[0] = nums[0];
  21.         dp_no_last[1] = nums[0] > nums[1] ? nums[0] : nums[1];
  22.         dp_no_last[ nums.size()-1 ] = 0;
  23.         for(int i = 2; i < nums.size()-1; i++) {
  24.             int take_it = nums[i] + dp_no_last[i-2];
  25.             int no_take = dp_no_last[i-1];
  26.             dp_no_last[i] = take_it > no_take ? take_it : no_take;
  27.         }
  28.         int max_no_last = *max_element(dp_no_last, dp_no_last + nums.size());
  30.         delete[] dp_no_first; 
  31.         delete[] dp_no_last;
  32.         return max_no_first > max_no_last ? max_no_first : max_no_last;
  33.     }
  34. };