House Robber (II)

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. The houses are arranged in a circle (hence last house and first house are adjacent).

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.

If the robber robbed the first house he can't rob the last one otherwise he can. Hence we use two dp lists, one with first house robbed and the second without first house robbed.

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 two list with size equal the number of houses
    dp = [[0 for _ in range(len(nums))] for _ in range(2)]
    dp[0][0], dp[0][1] = nums[0], max(nums[0], nums[1]) # first list where first house can be robbed (and last house can't)
    dp[1][0], dp[1][1] = 0, nums[1] # second list where first house can't be robbed (and last house can)

    # loop over each house starting with 3rd one until penultimate house
    for i in range(2, len(nums)-1):
        dp[0][i] = max(dp[0][i-1], dp[0][i-2] + nums[i]) # maximum amount is max between precendent house amount and i-2 house amount + current house amount
        dp[1][i] = max(dp[1][i-1], dp[1][i-2] + nums[i]) # maximum amount is max between precendent house amount and i-2 house amount + current house amount

    dp[0][-1] = dp[0][-2] # in first list last house can't be robbed so its amount is the same as penultimate house 
    dp[1][-1] = max(dp[1][-2], dp[1][-3] + nums[-1]) # in the second list we can apply the classic method

    # max amount is the max of the two strategies: 1) rob first and not last and 2) rob last and not first
    return(max(dp[0][-1], dp[1][-1]))