class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> f(nums.size());
        auto g = f;

        int ret = 0;
        f[0] = nums[0]; g[0] = 0;
        for(int i = 1; i < nums.size(); ++i)
        {
            f[i] = g[i-1] + nums[i];
            g[i] = max(g[i-1],f[i-1]);
        }

        return max(f[nums.size()-1], g[nums.size()-1]);
    }
};

//状态表示：f[i] 表示该位置选时，偷到该位置的最大值
//         g[i] 表示该位置不选时，偷到该位置的最大值