House Robber (I)

The intput represents the list of houses with the amount to rob in each of them. The robber must maximise the amount to rob but it can't rob two adjacent houses otherwise the police will be called.

For house i the maximum amount to rob is the maximum between the amount robbed for house i-1 and the amount robbed for house i-2 plus the amount that can be rob in this house.

def rob(nums: List[int]) -> int:
    # if there is two houses or less just return the amount of the house with maximum amount
    if len(nums) <= 2:
        return(max(nums))

    # initialize the dp list with maximum value robbed in 1st and 2nd house + 0 for other
    dp = [nums[0]] + [max(nums[0], nums[1])] + [0 for _ in range(len(nums)-2)]
    
    # loop over each house starting with 3rd one
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]) # maximum amount is max between precendent house amount and i-2 house amount + current house amount
        
    return(dp[-1])