// Steve Yang
// 2019.09.28
class Solution {
public:
    int robi(vector<int>& nums, int i, vector<int>& sum) {
        if (i >= nums.size()) {
            return 0;
        }

        int c1 = (0 <= sum[i] ? sum[i] :
                    (sum[i] = nums[i] + robi(nums, i+2, sum)));

        int c2 = (i+1 >= nums.size() ? 0 :
                       (0 <= sum[i+1] ? sum[i+1] :
                        (sum[i+1] = nums[i+1] + robi(nums, i+3, sum))));

        return c1 >= c2 ? c1 : c2;

    }
    int rob(vector<int>& nums) {
        vector<int> sum(nums.size(), -1);
        if (1 == nums.size()) {
            return nums[0];
        }
        return robi(nums, 0, sum);
    }
};