# 198 - House Robber

解法一 - DP

先定義一下 subproblem:

dp[i] = 搶到第 i 間房子，能夠搶到最大值

所以就分成要搶第 i 間 and 不要搶第 i 間兩種情況，如果

• 要搶第 i 間：賺到的錢就是 dp[i-2] + nums[i]

• 不要搶第 i 間：賺到的錢就是 dp[i-1]

dp[i] = max(dp[i-2]+nums[i], dp[i-1])

實作出來就是：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n <= 0) return 0;

        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = nums[0];

        for(int i=2; i<=n; i++)
            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]);

        return dp[n];
    }
};