# 198. House Robber

{% hint style="info" %}
Comes from Google interview. Classical DP problem. 
{% endhint %}

### Solution 1: regular sequence DP array. 

1. robs\[x] means the max money can rob in `house [0:x]`
2. Initialize `robs[0]` and `robs[1]`. Initialize as much as possible.
3. Time complexity = $$O(n)$$ , spcase complexity = $$O(n)$$ 

![When robber wants to rob (2, 7, 9, 3, 1) houses, two options: (2, 7, 9, 3) or (2, 7, 9) + 1](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MB74QkwEJtoqmzcdHCI%2F-MB7QvxWX5lUVwqQCLKg%2F1593574297604.jpg?alt=media\&token=d4ba07bf-973c-4768-8bbf-c8ae36a21cd1)

{% tabs %}
{% tab title="C++" %}

```cpp
class Solution {
public:
    int rob(vector<int>& nums) {
    // edge case
        if(nums.empty()) return 0;
        if(nums.size() == 1) return nums.at(0);
        
        int robs[nums.size()];
        robs[0] = nums.at(0);
        robs[1] = max(nums.at(0), nums.at(1));
        for(int i = 2; i < nums.size(); i ++) {
            robs[i] = max(robs[i-2]+nums.at(i), robs[i-1]);
        }
        
        return robs[nums.size()-1];
    }
};
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}

### Solution 2: optimize space complexity, because the previous robs are not useful

1. Only `robs[x-2]` and `robs[x-1]` are used for computing `robs[x]`.
2. Initialization is important.
3. Time complexity = $$O(n)$$ , space complexity = $$O(1)$$&#x20;

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MB7UrhvZbP-DQbNqhOo%2F-MB7Vd6_ns9JPh1q5gkM%2F1593575622878.jpg?alt=media\&token=dfe5ffbb-3816-4da1-a50f-82d6179335e1)

{% tabs %}
{% tab title="C++" %}

```cpp
class Solution {
public:
    int rob(vector<int>& nums) {
        // edge case
        if(nums.empty()) return 0;
        // rob1 is two before current rob, rob2 is one before current rob
        int rob1, rob2 = 0;
        for(int i = 0; i < nums.size(); i ++) {
            int temp = max(rob1 + nums[i], rob2);
            rob1 = rob2;
            rob2 = temp;
            
        }
        
        return rob2;
    }
};
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}