題目：
你是小偷，計劃偷一排房子。每個房子裡都有一定數量的現金，然而，你不能連續偷兩間相鄰的房子，否則會被發現。你的目標是偷取最多的現金，該如何決策呢？

解題思路

nums = [2,7,9,3,1]
一步一步計算最大現金：
dp[0] = 2（偷第一間房子）。
dp[1] = max(2, 7) = 7（偷第二間房子）。
dp[2] = max(7, 2 + 9) = 11（選擇偷第三間房子，因為 7 < 2 + 9）。
dp[3] = max(11, 7 + 3) = 11（選擇不偷第四間房子，因為 11 > 7 + 3）。
dp[4] = max(11, 11 + 1) = 12（選擇偷第五間房子，因為 11 + 1 = 12）。

因此可以推論出以下結果，
目前房子可以偷到的最大金額 = max(前一棟可以偷到的最大金額, 前前棟可以偷到的最大金額 + 現在這棟金額)
即 dp[i] = max(dp[i-1], dp[i-2] + num[i])

實作：

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

        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.size()-1];
    }
};

時間複雜度：O(n)
空間複雜度：O(n)

發現每一步只需要 dp[i-1] 與 dp[i-2]，所以改用兩個變數來存就好，而不用存下整個 dp 陣列，
進一步優化空間程式碼如下，

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

        int prev2 = nums[0]; // dp[i-2]
        int prev1 = max(nums[0], nums[1]); // dp[i-1]
        for (int i = 2; i < nums.size(); i++) {
            int curr = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

時間複雜度：O(n)
空間複雜度：O(1)

參考：
#198. House Robber