Medium

House Robber II

LAB

Return the most money that can be robbed from circularly arranged houses without robbing adjacent houses.

EXAMPLES

Example 1

Input
{
  "nums": [
    2,
    3,
    2
  ]
}

Output
3

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Split into two cases: either rob house 0 (then solve linear problem on [2, n-2]) or don't rob house 0 (solve on [1, n-1]).

Reveal reference solution +

pythonREFERENCE

def rob(self, nums: List[int]) -> int:
    n = len(nums)
    if n == 1: return nums[0]

    @cache
    def dp(i, min_idx):
        if i < min_idx: return 0
        return max(nums[i] + dp(i-2, min_idx), dp(i-1, min_idx))

    # Case 1: Rob house 0 → can't rob house 1 or n-1
    # Case 2: Don't rob house 0 → can rob houses 1 to n-1
    return max(nums[0] + dp(n-2, 2), dp(n-1, 1))

TimeO(n)

SpaceO(n)

Open on LeetCode ↗