# House Robber II

## Question

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.

Notice

This is an extension of House Robber.

Example

nums = [3,6,4], return 6

Tags

Dynamic Programming Microsoft

Related Problems

Medium House Robber III 28 % Medium Paint House 35 % Easy Paint Fence 28 % Medium House Robber

## Analysis

House Robber的延伸问题，将线性（linear）排列改成环形（cycle），DP的策略需要进行相应的调整，由于定义了不能选择相邻的房子，可以分别计算两种情况，一个选择`nums[0]`，那么就不能选择`nums[nums.length]`，或者选择`nums[nums.length]`，就不可以选择`nums[0]`，这样，环形的问题就分解成为两个线性问题，最后取两个结果中的最大值即可。

``nums = [3,6,4]``

``[3,6,X]``

``[X,6,4]``

## Solution

``````public class Solution {
/**
* @param nums: An array of non-negative integers.
* return: The maximum amount of money you can rob tonight
*/
public int houseRobber2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length < 2) {
return nums[0];
}

int[] first = new int[nums.length + 1]; // Start with first house
int[] second = new int[nums.length + 1]; // Start with second house

first[0] = 0;
first[1] = nums[0];
second[0] = 0;
second[1] = 0;

for (int i = 2; i <= nums.length; i++) {
first[i] = Math.max(first[i - 1], first[i - 2] + nums[i - 1]);
second[i] = Math.max(second[i - 1], second[i - 2] + nums[i - 1]);
}
return Math.max(first[nums.length - 1], second[nums.length]);
}
}``````

Utilizing House Robber I

``````public class Solution {
/**
* @param nums: An array of non-negative integers.
* return: The maximum amount of money you can rob tonight
*/
public int houseRobber2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length < 2) {
return nums[0];
}

return Math.max(houseRobber(nums, 0, nums.length - 2), houseRobber(nums, 1, nums.length - 1));
}

public int houseRobber(int[] A, int start, int end) {
if (A == null || A.length == 0) {
return 0;
}

if (start == end) {
return A[start];
}
if (start + 1 == end) {
return Math.max(A[start], A[end]);
}

// Define DP state
int[] dp = new int[end - start + 2];

// Initialize DP
dp[start] = A[start];
dp[start + 1] = Math.max(A[start], A[start + 1]);

// DP Function
for (int i = start + 2; i <= end; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + A[i]);
}
return dp[end];
}
}``````

if not liking the dp[start], dp[start + 1] expression in houseRobber() function, the following uses a more intuitive way of expression:

``````    public int rob1(int[] nums, int start, int end) {
if (nums == null || nums.length == 0) {
return 0;
}
if (start == end) {
return nums[start];
}
if (start + 1 == end) {
return Math.max(nums[start], nums[end]);
}
int[] dp = new int[end - start + 2];
dp[0] = nums[start];
dp[1] = Math.max(nums[start], nums[start + 1]);

for (int i = start + 2; i <= end; i++) {
dp[i - start] = Math.max(dp[i - start - 1], dp[i - start - 2] + nums[i]);
}
return dp[end - start];
}``````

Utilize House Robber I with Rolling Array Optimization

``````public class Solution {
public int houseRobber2(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
return Math.max(houseRobber1(nums, 0, nums.length - 2), houseRobber1(nums, 1, nums.length - 1));
}

public int houseRobber1(int[] nums, int st, int ed) {
int []res = new int[2];
if(st == ed)
return nums[ed];
if(st+1 == ed)
return Math.max(nums[st], nums[ed]);
res[st%2] = nums[st];
res[(st+1)%2] = Math.max(nums[st], nums[st+1]);

for(int i = st+2; i <= ed; i++) {
res[i%2] = Math.max(res[(i-1)%2], res[(i-2)%2] + nums[i]);

}
return res[ed%2];
}
}``````

Last updated