## House Robber II

07/16/2016 Dynamic Programming

## Question

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.

## Solution

Result: Accepted Time: 0 ms

Here should be some explanations.

class Solution {
public:
int rob(vector<int>& nums) {
int ret = 0;
const int sz = nums.size();
if(sz < 4)
{
for(auto x:nums)
ret = max(x,ret);
return ret;
}
int dp[4]={0,nums[1],nums[2],nums[3]};
for(int i = 3; i < sz; i++)
dp[i&3]=nums[i] + max(dp[(i-2)&3],dp[(i-3)&3]);
ret = max(dp[(sz-1)&3],dp[(sz-2)&3]);
nums[sz - 1] = 0;
for(int i = 0; i < 4; i++)
dp[i] = nums[i];
dp[2]+= dp[0];
for(int i = 3; i < sz; i++)
dp[i&3]=nums[i] + max(dp[(i-2)&3],dp[(i-3)&3]);
ret = max(ret,max(dp[(sz-1)&3],dp[(sz-2)&3]));
return ret;
}
};


Complexity Analytics

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$