You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

解法：這是一道簡單題，使用動態(tài)規(guī)劃方法可求解。注意到sum[n]=max{sum[n-1], sum[n-2]+an},為了節(jié)省內(nèi)存，我們可以使用兩個臨時變量來保存需要的臨近兩個和。

class Solution {
public:
    //sum[n] = max{sum[n-1], sum[n-2]+an}
    int rob(vector<int>& nums) {
        if(nums.size() == 0) {
            return 0;
        }
        if(nums.size() == 1) {
            return nums[0];
        }
        
        int firstSum = nums[0];
        int secondSum = max(nums[0],nums[1]);
        for(int i=2; i<nums.size(); i++) {
            int temp = secondSum;
            secondSum = max(secondSum, firstSum+nums[i]);
            firstSum = temp;
        }
        return secondSum;
    }
};

這個問題變一下形，如果房子首尾相連，還是不能夠同時搶劫相鄰的房子，那么該怎樣才能搶到的錢最多呢？
解法：實際上，首尾相連的房子我們可以拆成兩個直線房子的子問題。考慮到包含第一個房子，則必然不包含最后一個房子，而包含最后一個房子則必然不包含第一個房子。因此 sum = max(sum(1, n-1), sum(2, n))；這里每一個子問題又退化成之前的簡單題，從而可以順利求解。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) {
            return 0;
        }
        
        if(n == 1) {
            return nums[0];
        }
        
        if(n == 2) {
            return max(nums[0], nums[1]);
        }
        
        int firstSum = subRob(nums, 0, n-1);
        int secondSum = subRob(nums, 1, n);
        return max(firstSum, secondSum);
    }
    
    int subRob(vector<int>nums, int start, int end) {
        int firstSum = nums[start];
        int secondSum = max(nums[start+1], firstSum);
        for(int i=start+2; i<end; i++) {
            int temp = secondSum;
            secondSum = max(firstSum+nums[i], secondSum);
            firstSum = temp;
        }
        return secondSum;
    }
};

在實際編程的時候，依然要注意驗證邊界的情況！