198. House Robber

Example 1:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).  

Total amount you can rob = 1 + 3 = 4.

 

Example 2:

Input: nums = [2,7,9,3,1]

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).  

Total amount you can rob = 2 + 9 + 1 = 12.

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ####### Initialization #######
        length = len(nums)
        if length==0:
            return 0
        if length==1:
            return nums[0]
        if length==2:
            return max(nums)
			
        dp = [0]*length # assign dp array
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        
        ###### More than 3 length of list ########
        for i in range(2, length):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]) 
            # new dp = max(two steps before + current value, one step before dp)
        print(dp)
        
        return max(dp)