# 198.打家劫舍

## 问题描述
[198.打家劫舍](https://leetcode.cn/problems/house-robber/)

## 解题思路
`dp[i]`表示考虑前`i`个房间，能窃取到的最大金额。

考虑递推关系:
- 假设第要窃取第`i`个房间，那么说明第`i - 1`个房间，肯定没有被窃取，`dp[i] = dp[i - 2] + nums[i - 1]`。
- 假设不窃取第`i`个房间，则`dp[i] = dp[i - 1]`。

综上，`dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])`。

## 代码
```cpp
#include <vector>
using std::vector;
class Solution {
  private:
    int max(int a, int b) {
        return a > b ? a : b;
    }

  public:
    int rob(vector<int> &nums) {
        vector<int> dp(nums.size() + 1, 0);
        if (nums.size() == 1)
            return nums[0];
        if (nums.size() == 2)
            return nums[0] > nums[1] ? nums[0] : nums[1];
        dp[1] = nums[0];
        for (int i = 2; i <= nums.size(); i++) {
            dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }
        return dp[nums.size()];
    }
};
```