# 198. House Robber (Easy)

## 1.問題 

* 你是位專業的強盜, 計畫搶劫一條街上的房子. 每間房子都存有各自的金額, 唯一的限制是相鄰的房子的保全系統是相連的, 而且若相鄰的房子遭破壞時將會自通知警察
* 給予一個代表每間房子內金額的list, **找出不被報警下可搶得的最大金額**

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LHSHG4LUGIOYGwggPXN%2F-LHSKNmdHryZVwooC0DL%2F2018071501.jpg?alt=media\&token=4f59b678-3dd2-4ddb-8aea-b8a0ac0c541b)

## 2.想法 

* Dynamic programming
  * 迴圈list中的所有店家:
    * 每回合要選擇可以賺最多錢的選項
      * 1.到前前家為止所儲存錢 + 偷這一間的錢
      * 2.到前家為止所儲存錢 + 不偷這一間的錢

## 3.程式碼 

```
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() <= 1)
        {
            return nums.size() == 0 ? 0 : nums[0];
        }
        int lastTime = 0, secondLastTime = 0;
        for (int l = 0; l < nums.size(); l++)
        {
            int recordLastTime = lastTime, recordSecondLastTime = secondLastTime;
            secondLastTime = recordLastTime + nums[l];
            lastTime = max(recordLastTime, recordSecondLastTime);
        }
        return max(lastTime, secondLastTime);
    }
};
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LHSHG4LUGIOYGwggPXN%2F-LHSY2A0VJzRdOZjQmqD%2F2018071502.jpg?alt=media\&token=f900abbc-a8f0-436d-9d07-cfc008a85da1)