# 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

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++

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);
    }
};

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++

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