# 213. House Robber II

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MetEx1BX6tUX-4XTlAq%2F-MetkYyxd0NzKfhd8CVu%2Fimage.png?alt=media\&token=07ca2edf-c057-4ffa-baf8-c1ee57f2510f)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MetEx1BX6tUX-4XTlAq%2F-MetkbxnUN119_QK2_ma%2Fimage.png?alt=media\&token=a32b3261-08c2-460e-a904-655fea8a865e)

All houses at this place are **arranged in a circle.** That means the first house is the neighbor of the last one.&#x20;

so it means, we can define two cases with House Rober 1

1. rob first house
2. rob last house

solution:&#x20;

dpFunction is the solution of **198. House Robber**

```java
Math.max(dpFunction(rob first house), dpFunction(rob last house))
```



time: O(n)

space: O(n)

```java
class Solution {
    public int rob(int[] nums) {
        // arranged in a circle.
        // 1. steal first house
        // 2. steal last house
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(robDP(Arrays.copyOfRange(nums, 0, nums.length - 1)), robDP(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    
    public int robDP(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int n = nums.length;
        int dp[] = new int[n];
        
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        int res = Math.max(dp[0], dp[1]);
        
        for (int i = 2 ; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
```

\----

time: O(n)

space:O(1)

```java
class Solution {
    public int rob(int[] nums) {
        // arranged in a circle.
        // 1. steal first house
        // 2. steal last house
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(robDP(Arrays.copyOfRange(nums, 0, nums.length - 1)), robDP(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    
    public int robDP(int[] nums) {
        int prevMax = 0;
        int currMax = 0;
        
        for (int num : nums) {
            int temp = currMax;
            currMax = Math.max(currMax, prevMax + num);
            prevMax = temp;
        }
        return currMax;
    }
}
```



## use this one!

```java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(
            rob(nums, 0, nums.length-2), 
            rob(nums, 1, nums.length-1)
        );
    }
    private int rob(int[] nums, int start, int end) {
        int dpi2 = 0;
        int dpi1 = 0;
        int dpi = 0;
        
        for (int i = end; i >= start; i--) {
            dpi = Math.max(dpi1, nums[i] + dpi2);
            dpi2 = dpi1;
            dpi1 = dpi;
        }
        return dpi;
    }
}

/*
so the range become different

 n       n 
[x,x,x,x,x]
 n
         n
         
3 cases to match questions

so we can only 
max(
rob(1 ~ n-1),
rob(1 ~ n)
rob(0 ~ n-1)
)
compare which one is bigger

we can ignore this one, rob(1 ~ n-1), this one must be smaller than other 2.

*/
```
