#198 打家劫舍(动态规划)

198. 打家劫舍 - 力扣（LeetCode）

状态：dp[i]，从0开始，偷到i时（0..i每家都可以选择偷/不偷），能获取的最大收益。

初始状态：dp[0...2]可以直接给出。

转移方程：dp[i]=nums[i]+max(dp[0...i-2)。

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

        int max=0;
        for(int i=0;i<nums.size();i++)
            if(dp[i]>max)  max=dp[i];
        return max;
    }
};