198. Looting - Dynamic Planning

One 、 Title Description

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 .

Two 、 Problem solving

Dynamic programming

dp[i] Indicates that the subscript is i The maximum value that can be stolen when it is a subscript .
dp[i]=max(dp[i−2]+nums[i],dp[i−1])

class Solution {
    
    public int rob(int[] nums) {
    
        // The idea of solving problems is relatively simple   According to the formula 
        //dp[i]=max(dp[i−2]+nums[i],dp[i−1])
        int length = nums.length;
        if(length == 0 || nums == null){
    
            return 0;
        }
        if(length == 1){
    
            return nums[0];
        }
        int[] dp = new int[length+1];
        dp[1] = nums[0];
        for(int i = 2;i<=length;i++){
    
            dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
        }
        return dp[length];
    }
}