## 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.
```

## Solutions

抢劫时不能连续抢两家，不然会触发报警。

### 1. DP

在学回溯的时候，看到什么就觉得都该用回溯做，结果纠结半天没想出来。这里只要用动规求解就好了，主要是要分清楚状态转移矩阵：`dp[i]=max(nums[i]+dp[i-2], dp[i-1])`

。

要分清求最值的几种方法，DP，BFS，贪心等。

```
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums or len(nums) <= 0:
return 0
elif len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums[0], nums[1])
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[-1]
```