# 198. House-Robber

difficulty: Easy

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

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**.

&#x20;

**Example 1:**

<pre><code>Input: nums = [1,2,3,1]
<strong>Output:
</strong> 4
<strong>Explanation:
</strong> Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
</code></pre>

**Example 2:**

<pre><code>Input: nums = [2,7,9,3,1]
<strong>Output:
</strong> 12
<strong>Explanation:
</strong> Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.
</code></pre>

&#x20;

**Constraints:**

* `0 <= nums.length <= 100`
* `0 <= nums[i] <= 400`

## Method One

```
class Solution {
    public int rob(int[] nums) {
        if( nums.length < 1 ) {
            return 0;
        }
        int[] dp = new int[nums.length];
        for(int i = 0; i < nums.length; i++ ) {
            int prePre = i - 2 < 0 ? 0 : dp[i - 2];
            int pre = i - 1 < 0 ? 0 : dp[ i - 1 ];
            dp[i] = Math.max(prePre + nums[i], pre);
        }
        return dp[nums.length - 1];
    }
}
​
/**
index 0 1 2 3 4
value 3 6 9 2 8
dp[0] = nums[0];
dp[1] = Math.max(  nums[1], dp[0] );
dp[2] = Math.max(dp[0] + nums[2], dp[1]);
...
dp[i] = Math.max( dp[i - 2] + nums[i], dp[ i - 1 ] );
*/
​
​
```

当然很轻松就可以化成 O(1) 的。

```java
class Solution {
    public int rob(int[] nums) {
        if( nums.length < 1 ) {
            return 0;
        }
        int prePre = 0;
        int pre = 0;
        for(int i = 0; i < nums.length; i++ ) {
            int temp = pre;
            pre = Math.max( prePre + nums[i], pre);
            prePre = temp;
        }
        return pre;
    }
}
```

2022 写的答案。 注意一个很重要的观察是，对于house robber来说，这个动态规划的结果永远有 dp\[x] >= dp\[x - 1]. 因此在skip当前房子的情况下，只需要看 dp\[x - 1]就好了。

```java
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        // RobCurrent = check n - 2 + curVal
        // SkipCurrent = check n - 2 and n - 1
        // max(rob, skip)
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i <= nums.length; i++){
            int robCurHouse = dp[i - 2] + nums[i - 1];
            // int skip = Math.max(dp[i - 1], dp[i - 2]);
            int skipCurHouse = dp[i - 1]; // since dp[i - 1] >= dp [i - 2];
            dp[i] = Math.max(robCurHouse, skipCurHouse);
        }
        return dp[nums.length];
    }
}
```
