---
# System prepended metadata

title: LC 198. House Robber
tags: [medium, leedcode, DP, python, c++]

---

# LC 198. House Robber

### [Problem link](https://leetcode.com/problems/house-robber/)

###### tags: `leedcode` `python` `c++` `medium` `DP`

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 systems connected and  **it will automatically contact the police if two adjacent houses were broken into on the same night** .

Given an integer array <code>nums</code> representing the amount of money of each house, return the maximum amount of money you can rob tonight  **without alerting the police** .

**Example 1:** 

```
Input: nums = [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: nums = [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.
```

 **Constraints:** 

- <code>1 <= nums.length <= 100</code>
- <code>0 <= nums[i] <= 400</code>


## Solution 1 - DP
#### Python
```python=
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return max(nums)

        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

        return dp[-1]
```
#### C++
```cpp=
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> cache(n, -1);

        function<int(int)> dfs = [&](int i) {
            if (i < 0) {
                return 0;
            }
            if (cache[i] != -1) {
                return cache[i];
            }
            cache[i] = max(dfs(i - 1), dfs(i - 2) + nums[i]);
            return cache[i];
        };
        return dfs(n - 1);
    }
};
```
```cpp=
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 2, 0);
        for (int i = 0; i < n; i++) {
            dp[i + 2] = max(dp[i + 1], dp[i] + nums[i]);
        }
        return dp[n + 1];
    }
};
```
## Solution 2 - DP
#### C++
```cpp=
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int f0 = 0;
        int f1 = 0;
        for (int i = 0; i < n; i++) {
            int f2 = max(f0 + nums[i], f1);
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
};
```

>### Complexity
>n = nums.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(n)             |
>| Solution 2  | O(n)            | O(1)             |


## Note
x
