#213 打家劫舍 II(动态规划)

213. 打家劫舍 II - 力扣（LeetCode）

同#198，但是dp[n-1]不能直接生成，需要新列一个不包含nums[0]的新dp，用新dp更新dp[n-1]

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() <= 3) {
            int max = 0;
            for (int x : nums) if (x > max) max = x;
            return max;
        }
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[2]+dp[0];
        //update dp (except dp[n-1])
        for(int i=3;i<nums.size()-1;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;
        }
        //update dp[n-1]( except 0)
        vector<int> dp1(nums.size(), 0);
        dp1[1] = nums[1];
        dp1[2] = nums[2];
        for(int i=3;i<nums.size();i++){
            int max=0;
            for(int j=1;j<i-1;j++){
                if(dp1[j]>max) max=dp1[j];
            }
            dp1[i]=nums[i]+max;
        }
        dp[nums.size()-1]=dp1[nums.size()-1];

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