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]，这样，环形的问题就分解成为两个线性问题，最后取两个结果中的最大值即可。
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];
}
}