LeetCode＃198. raid homes and plunder houses

subject (LeetCode):

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 .

The practice of this problem is dynamic programming , We can compare LeetCode#53. Maximum subarray and _ As the wind Zhhh The blog of -CSDN Blog

How to do it , You will find that they have many similarities , We also use dp[i] Before presentation i The maximum value obtained by item .

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==1:   # List the special situations first ①
            return nums[0]
        elif len(nums)==2: # A special case ②
            return max(nums)
        dp=[0]*len(nums)   # When len(nums)>2 when 
        dp[0]=nums[0]      # If only 1 home , Get the value of the first house 
        dp[1]=max(nums[0],nums[1]) # The first two get the maximum of them 
        for i in range(2,len(nums)):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]) # If the first i Home theft , Before getting i-1 Home maximum 
        return dp[len(nums)-1]                 # If the first i Home does not steal , Before getting i-2 Home maximum and number i Home value