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.

解法：这是一道简单题，使用动态规划方法可求解。注意到sum[n]=max{sum[n-1], sum[n-2]+an},为了节省内存，我们可以使用两个临时变量来保存需要的临近两个和。

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;
    }
};

在实际编程的时候，依然要注意验证边界的情况！