---
# System prepended metadata

title: Leetcode 198. House Robber
tags: [Leetcode(C++)]

---

# Leetcode 198. House Robber
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/house-robber/ 。

想法 : 

    陣列所代表的狀態 : 在這間房子已經偷到的最大金額。
    
    有兩種轉移，一種是不偷這間，另外一種是偷這間，如果不偷這間那最大值跟上一間一樣，如果偷這 
    間就一定是前2間已經偷到的金額加上這間。

時間複雜度 : O(n)。

程式碼 :

```
class Solution {
public:
    int rob(vector<int>& nums) {
        int house[410]={0},l=nums.size();
        house[0]=nums[0]; 
        if(l >= 2) house[1]=max(nums[0],nums[1]);
        
        
        cout << l << endl;
        for(int i=2 ; i<l ; i++){
            house[i]=max(house[i-1],house[i-2]+nums[i]);
        }
        
        
        return house[l-1];
    }
};
```