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]);
        }
        vector<int> dp(nums.size() + 1, 0);
        dp[1] = nums[0];
        dp[2] = max(nums[0], nums[1]);
        for(int i =  3; i <= nums.size(); i++){
            // 偷不偷第ｉ个房屋，偷的话则是dp[i -2] + nums[i-1]
            // 不偷的话，则是dp[i - 1]
            //　所以状态转移方程为　dp[i] = max(dp[i - 1], dp[i -2] + nums[i-1])
            dp[i] = max(dp[i - 1], dp[i -2] + nums[i-1] );
        }
        return dp[nums.size()];
    }
};

优化版本

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 dp0 = nums[0];
        int dp1 = max(nums[0], nums[1]);
        int dp2 = 0;
        for(int i = 3 ; i<= nums.size(); i++){
            dp2 = max(dp1, dp0 + nums[i-1]);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp2;
    }
};