> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/binary-search-and-tree/198.-house-robber.md).

# 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](/files/-MB7QvxWX5lUVwqQCLKg)

{% 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;

![](/files/-MB7Vd6_ns9JPh1q5gkM)

{% 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 %}