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]

第一种，选nums[0]

[3,6,X]

第二种，选nums[nums.length]

[X,6,4]

为了下标的标注方便，统一两个DP数组的长度，只不过在最终的统计结果时，选nums[0]取DP数组的first[nums.length - 1], 而选nums[nums.length]，则取DP数组中的second[nums.length]。

另外，因为是I的延伸题，I中所运用的DP可以被复用，只需要设定起始点和终点，那么问题II，就可以直接拆解为两个不同起始点和终点的问题I。 https://discuss.leetcode.com/topic/14375/simple-ac-solution-in-java-in-o-n-with-explanation

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];
    }
}

Reference

• LeetCode discuss: Simple AC solution in Java in O(n) with explanation

• Jiuzhang