leetcode Question: House Robber II

House Robber II

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.

Analysis:

Please read my previous post for the original version of the House Robber problem (link). 

In this problem, a new requirement is added :   the houses are in a circle.  In other words, previously we could rob the first house and it is OK to also rob the last one. But now since the last house and the first house are now adjacent, it is not allowed to rob those two houses at the same time. From the figure below, one can see that, different from previous version, now the path (arrows after house #4) has new connections to the front. 

Considering  the “states” in the last house, if we choose to rob it, when we go to the first house, now the only action we have is to NOT rob it. In other words, for the first house, we will never have the amount of money if we have robbed the last one. This can also be viewed as: We have never seen the first house, but search and rob houses from 2nd to the last. 

On the other hand, if we choose not to rob the last house, when we go to the first house, the actions are rob or not rob, which is common. Look at the last house, we are sure that we will NOT rob this house, then similarlly the probem becomes searching and robbing from 1st to the last -1 house. 

Obviously, in the above two cases, the larger result is the final value we want.

Code (C++):

class Solution {

public:

int rob(vector<int>& nums) {

int sz = nums.size();

int r = 0;

if (sz == 0) {return 0;}

if (sz < 4) {

for (int i=0;i<sz;i++){

r = max(r, nums[i]);

}

return r;

}

// From 0 to n-1

vector<int> res(sz,0);

res[0] = nums[0];

res[1] = max(nums[1],nums[0]);

int i=2;

while (i < sz-1){

res[i] = max(res[i-1], res[i-2] + nums[i]);

i++;

}

r = res[sz-2];

// From 1 to n

res.clear();

res[1] = nums[1];

res[2] = max(nums[1],nums[2]);

i = 3;

while (i<sz){

res[i] = max(res[i-1], res[i-2] + nums[i]);

i++;

}

return max(r, res[sz-1]);

}

};

Code (Python):

class Solution(object):

def rob(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

sz = len(nums)

if sz == 0:

return 0

if sz < 4:

return max(nums)

res = [0 for x in range(sz)]

res[0] = nums[0]

res[1] = max(nums[0],nums[1])

r = 0

i = 2

while i < sz - 1:

res[i] = max(res[i-1], res[i-2] + nums[i])

i+=1

r = res[sz-2]

res = [0 for x in range(sz)]

res[1] = nums[1]

res[2] = max(nums[2],nums[1])

i = 3

while i < sz:

res[i] = max(res[i-1], res[i-2] + nums[i])

i+=1

return max(r, res[sz-1])