[213] 打家劫舍 II

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() <= 0){
            return 0;
        }
        if(nums.size() == 1){
            return nums[0];
        }
        if(nums.size() == 2){
            return max(nums[0], nums[1]);
        }
        int n = nums.size();
        //把问题分解成是否打劫第一家
        //打劫了第一家，则不能打劫最后一家
        return max(robRange(nums, 0, n-2), 
                   robRange(nums, 1, n-1));
    }
    int robRange(vector<int>& nums, int start, int end){
        int dp_i = 0;
        int dp_i_2 = 0;
        int dp_i_1 = 0;
        // for(int i = end; i>= start; i--){
        //     dp_i = max(dp_i_1, dp_i_2 + nums[i]);
        //     dp_i_2 = dp_i_1;
        //     dp_i_1 = dp_i;
        // }
        // 采用自底向上的方式计算，能够减少内存消耗
        for(int i = start ; i<= end; i++){
            dp_i = max(dp_i_1, dp_i_2 + nums[i]);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
};