# 198. House Robber

[ **198. House Robber**](https://leetcode.com/problems/house-robber/description/)

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

**Example 1:**

```
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
```

**Example 2:**

```
Input: [2,7,9,3,1]
Output: 12
Explanation: 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.
```

***My Solutions:***

用dp做，可以用一个dp【】储存或者只用一个int lastP

dp【i】 = Math.max(dp\[i - 1], dp\[i - 2] +nums\[i - 1]) 表示可以

* 抢劫在当前之前的一家（不抢劫当前家庭）: dp\[i - 1]
* 或者抢劫当前家和之前skip 1的一家: dp\[i - 2] + nums\[i - 1]

```java
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len <= 0) return 0;
        int[] dp = new int[len + 1]; // 注意这里是+1
        dp[0] = 0; // rob nothing before house 1
        dp[1] = nums[0]; //house 1
        for (int i = 2; i <= len; i++) { //go through from house 2 //注意这里是i<=len
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])
        }
        return dp[len];
        
// 因为只需要记录两个数字，所以也可以直接用两个int variable记录        
// 假设【0,1,2】现在在2号家庭。lastP代表抢劫了0号家庭，profit代表抢劫了1号家庭
//         int lastP = 0, profit = 0;
//         for (int i = 0; i < nums.length; i++) {
//             int temp = lastP; // 抢劫skip 1前一家的利润
//             lastP = profit; // 抢劫上一家的利润
//             profit = Math.max(profit, nums[i] + temp); //表示当前可以获得的最大利润
//         }
//         return profit;
    }
}
```