# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/house_robber_ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.