198. house raiding

198. raid homes and plunder houses

You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm , The maximum amount that can be stolen overnight .

Example 1：

Input ：[1,2,3,1]
Output ：4
explain ： Steal 1 House No ( amount of money = 1) , And then steal 3 House No ( amount of money = 3).
Maximum amount stolen = 1 + 3 = 4 .
Example 2：

Input ：[2,7,9,3,1]
Output ：12
explain ： Steal 1 House No ( amount of money = 2), Steal 3 House No ( amount of money = 9), Then steal 5 House No ( amount of money = 1).
Maximum amount stolen = 2 + 9 + 1 = 12 .

reflection

Definition dp The meaning of array and its subscript

dp[i]: Before presentation i The maximum amount that can be stolen in days is dp[i]

initialization dp Array

initialization dp[0] and dp[1]

State transition equation

dp[i] = Max{dp[i-1], dp[i-2]+nums[i] }

class Solution {
    
        public int rob(int[] nums) {
    
       if(nums.length==1) return nums[0];

        //step 1  establish dp Array 
        int[] dp=new int[nums.length];

        // step 2  initialization dp Array 
        dp[0] = nums[0];
        if(nums[1]>nums[0])
            dp[1] = nums[1];
        else dp[1] = dp[0];
        if(dp.length==2) return dp[1];

        // step 3  perfect dp Array 
        for (int i=2;i<dp.length;i++){
    
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        
        return dp[dp.length-1];
    }
}