Skip to main content

House Robber II

Question​

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police, and without robbing any two adjacent houses.

Example 1
Input: [2,3,2]
Output: 3 (rob 2nd house)

Solution​

all//House Robber II.py


def houseRobber2(nums):
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return nums[0]
    if len(nums) == 2:
        return max(nums)

    # rob first and last
    dp1 = [0] * (len(nums)-1)
    dp1[0] = nums[0]
    dp1[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i])

    # not rob first and last
    dp2 = [0] * (len(nums)-1)
    dp2[0] = 0
    dp2[1] = nums[1]
    for i in range(2, len(nums)-1):
        dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i])

    return max(dp1[-1], dp2[-1])