> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/dynamic_programming/house_robber_ii.md).

# 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

```java
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

```java
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:

```java
    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

```java
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](https://discuss.leetcode.com/topic/14375/simple-ac-solution-in-java-in-o-n-with-explanation)
* [Jiuzhang](http://www.jiuzhang.com/solutions/house-robber-ii/)