213. house raiding II

raid homes and plunder houses II

You are a professional thief , Plan to steal houses along the street , There is a certain amount of cash in every room . All the houses in this place are Make a circle , This means that the first house and the last house are next to each other . meanwhile , Adjacent houses are equipped with interconnected anti-theft system , 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 device , The maximum amount you can steal tonight .

Example 1：

Input ：nums = [2,3,2]
Output ：3
explain ： You can't steal first 1 House No （ amount of money = 2）, And then steal 3 House No （ amount of money = 2）, Because they are next to each other .
Example 2：

Input ：nums = [1,2,3,1]
Output ：4
explain ： You can steal first 1 House No （ amount of money = 1）, And then steal 3 House No （ amount of money = 3）.
Maximum amount stolen = 1 + 3 = 4 .
Example 3：

Input ：nums = [1,2,3]
Output ：3

reflection

This question only needs to use 198 raid homes and plunder houses Before method acquisition of n-1 Maximum number of thefts per day and after n-1 Maximum number of thefts per day , Just take the maximum .

class Solution {
    
public int rob(int[] nums) {
    
        if(nums.length==1) return nums[0];
        if (nums.length==2) return Math.max(nums[0],nums[1]);
        int a=robTools(Arrays.copyOfRange(nums,0,nums.length-1));
        int b=robTools(Arrays.copyOfRange(nums,1,nums.length));
        return Math.max(a,b);

    }
    public int robTools(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];
    }
 }