# House Robber

## 198 House Robber

Given a list of non-negative integers represent the money in house, determine the maximum amount of money you can rob but not rob 2 continuous house

*   Space O(n)

    ```java
    public int rob(int[] nums) {
      int len = nums.length;
      if(len == 0) return 0;
      if(len == 1) return nums[0];

      int[] dp = new int[len];
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0], nums[1]);
      for(int i=2; i<len; i++){
          dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
      }
      return dp[len-1];
    }
    ```
*   Space O(1)

    ```java
    public int rob(int[] nums) {
      int curMax = 0;
      int preMax = 0;
      for(int n: nums){
          int tmp = curMax;
          curMax = Math.max(curMax, preMax + n);
          preMax = tmp;
      }
      return curMax;
    }
    ```

## 213. House Robber II

Same as house robber, but the first and the last house are connected

* Break the circle, find the max of dp\[n-1], dp\[n]

```java
public int rob(int[] nums) {
    if(nums.length == 0) return 0;
    if(nums.length == 1) return nums[0];
    return Math.max(helper(nums, 0, nums.length-1), helper(nums, 1, nums.length)); 
}

private int helper(int[] nums, int start, int end){
    int preMax = 0, curMax = 0;
    for(int i=start; i<end; i++){
        int tmp = curMax;
        curMax = Math.max(curMax, preMax + nums[i]);
        preMax = tmp;
    }
    return curMax;
}
```
