## House Robber I

* 一樣去思考 base case 和 subtask
* base case：在一開始，錢數是零
* subtask：搶到第 $i$ 個房子時可以有的最多錢
> $dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])$

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

## House Robber II
* 進階題，現在所有房子圍成一個環，即第一個房子和最後一個房子相鄰，所以頭尾最多只能偷一間
* 方法：針對 nums[0~n-2] 做一次 DP，nums[1~n-1] 再一次，並找出最大的

class Solution {
public:
    int rob(vector<int>& nums) {
        const int len = nums.size();
        vector<int> dp1(len,0);
        vector<int> dp2(len,0);
        if (len == 1) return nums[0];
        for (int i = 0;i<len-1;i++){
            if (i==0) dp1[i+1] = nums[i];
            else dp1[i+1] = max(dp1[i], dp1[i-1] + nums[i]);
        }
        cout<<"fjdk"<<endl;
        for (int i=1;i<len;i++){
            if (i==1) dp2[i] = nums[i];
            else dp2[i] = max(dp2[i-1], nums[i] + dp2[i-2]);
        }
        return max(dp1[len-1],dp2[len-1]);
    }
};