House Robber

198. House Robber

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.

S:DP 滚动指针

对nums[i]有rob和not rob两个选项。state：rob[i]为在i处rob能获得的最大收益，not_rob[i]为在处not rob能获得的最大收益。rob[i]时i-1必须是not rob，所以rob[i] = not_rob[i-1]+nums[i]。not_rob[i]时i-1可以是rob或者not rob。

    int rob(vector<int>& nums) {
        if(nums.size() < 1) return 0;
        int rob = nums[0], not_rob = 0;
        for(int i = 1; i < nums.size(); ++i){
            int pre_rob = rob;
            rob = not_rob + nums[i];
            not_rob = max(pre_rob, not_rob);
        }
        return max(rob, not_rob);
    }
//滚动指针写法：
    long long houseRobber(vector<int> A) {
        int n = A.size();
        if(n < 1) return 0;
        vector<long long> rob{0, A[0]};
        for (int i = 2; i <= n; ++i){
            rob[i%2] = max(rob[(i-1)%2], rob[(i-2)%2] + A[i-1]);
        }
        return rob[n%2];
    }

213. House Robber II Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.

S: DP 拆环

与house robber的唯一区别是，nums[0]和nums[size-1]不能同时抢。所以可以分两种情况：抢nums[0]，问题转化为用普通方法处理nums[0]到nums[size-2];不抢nums[0]，问题转化为用普通方法处理nums[1]到nums[size-1]。

    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size < 1) return 0;
        if(size == 1) return nums[0];
        else return max(rob1(nums, 0, size-2), rob1(nums, 1, size-1));
    }
    int rob1(vector<int>& nums, int start, int end){
        int rob = nums[start], not_rob = 0;
        for(int i = start+1; i <= end; i++){
            int pre_rob = rob;
            rob = not_rob + nums[i];
            not_rob = max(pre_rob, not_rob);
        }
        return max(rob, not_rob);
    }