House Robber II

Dynamic Programming1D DP

25 min

Problem Statement

You are a professional robber planning to rob houses along a street. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example

Example 1:

Houses are in a circle.

The first and last houses are neighbors.

Solution

Since the houses are in a circle, the first and last houses are adjacent. This means we can't rob both. To handle this, we can break the problem into two subproblems, both of which can be solved using the standard House Robber algorithm:

Rob houses from index 0 to n-2 (excluding the last house).
Rob houses from index 1 to n-1 (excluding the first house).

The final answer is the maximum of the results from these two subproblems. This approach correctly handles the circular dependency.

Algorithm Steps

If there's only one house, return its value.
Calculate the max loot for `nums[0...n-2]` using the standard House Robber DP approach.
Calculate the max loot for `nums[1...n-1]` using the standard House Robber DP approach.
Return the maximum of the two results.

Recurrence Relation

dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

House 1

House 2

House 3

House 4

House 5

Step: 1 / 5

House Robber II Solution


def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    def rob_linear(arr: list[int]) -> int:
        prev2, prev1 = 0, 0
        for num in arr:
            dp = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = dp
        return prev1

    # Rob houses from 0 to n-2 (exclude last)
    max1 = rob_linear(nums[:-1])
    
    # Rob houses from 1 to n-1 (exclude first)
    max2 = rob_linear(nums[1:])

    return max(max1, max2)