leetcode 198. 打家劫舍

dp
考虑了前一个房子进不进，发现想复杂了

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp( nums.size(),0);
        int ret = 0;
        bool qian = 0;
        if( nums.size() >= 1 ){
            dp[0] = nums[0];
            qian = 1;
            ret = max(dp[0],ret);
        }

        if( nums.size()>=2){
            if( nums[1] > nums[0]){
                dp[1] = nums[1];
                qian = 1;
            }else{
                dp[1] = nums[0];
                qian = 0;
            }
            ret = max(dp[1],ret);
        }
        
        for(int i=2;i < dp.size();i++){

            if( qian == 0 ){
                if( dp[i-1] > dp[i-2]){
                    dp[i] = dp[i-1] + nums[i];
                }else{
                    dp[i] = dp[i-2] + nums[i];
                }
                qian = 1;
            }else{
                if( dp[i-2] + nums[i] < dp[i-1]){
                    dp[i] = dp[i-1];
                    qian = 0;
                }else if(dp[i-2] + nums[i] >= dp[i-1]){
                    dp[i] = dp[i-2] + nums[i] ;
                    qian = 1;
                }
            }
            //debug( dp[i] )
            ret = max(ret,dp[i]);
        }
        return ret;
    }
};

dp[i] 表示前i个房子情况下，最大的值
状态转移方程：
dp[i] = max( dp[i-2] + nums[i-1],dp[i-1] );

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp( nums.size()+1,0);
        dp[0] = 0;
        if(nums.size()==0){
            return 0;
        }
        dp[1] = nums[0];
        for(int i = 2;i <= nums.size();i++){
            dp[i] = max( dp[i-2] + nums[i-1],dp[i-1] );
        }
        return dp[nums.size()];
    }
};