Leetcode: House Robber II

House Robber II

My Submissions

Total Accepted: 17938 Total Submissions: 62688 Difficulty: Medium

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Dynamic Programming

Show Similar Problems

```````````````````````````````````````````````````````````````````````````````````````````

DP:

Based on House Robber, we divide the input into two kinds:

e.g., nums= 1 2 3 5 4 3 2, we divide it into sub inputs:

            n1=  1 2 3 5 4 3 

            n2=     2 3 5 4 3 2, 

and then use the House Robber to run the two respectively and in then end choose the maximal one from the two results. 

/////////////////////////////////////////////////////////////////////////////

//codes

 class Solution {

 public:

int robSub(vector<int>& nums, int left, int right){

if (right - left == 0)return nums[left];

vector<int> dp;

int len = nums.size(), used = 0;

dp.assign(len, 0);

dp[left] = nums[left];

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

for (int i = left + 2; i <= right; i++){

if (nums[i] + dp[i - 2]>dp[i - 1]){

dp[i] = nums[i] + dp[i - 2];

}

else dp[i] = dp[i - 1];

}

return max(dp[right - 1], dp[right]);

}

int rob(vector<int>& nums) {

//check input

if (nums.empty())return 0;

if (nums.size() == 1)return nums[0];

int size = nums.size();

return max(robSub(nums, 0, size - 2), robSub(nums, 1, size - 1));

}

 };