House Robber II

Houses form a circle, so the first and last houses are neighbors.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

House Robber II: Break the circle into two endpoint-excluding lines, run take-or-skip DP on each, and keep the larger result.

Input and goalHouses form a circle, so the first and last houses are neighbors.

Split the circular constraintFor houses [1,2,3,1], any valid plan excludes house 3 or excludes house 0. Solve case A [1,2,3] and case B [2,3,1].

first102132last13

casesA excludes index 3; B excludes index 0

Recognize it

Use it when a linear adjacency DP gains one wraparound conflict between the first and last items; every feasible solution must omit at least one endpoint.

Keep true

Within each line, one_back is the best value through the current processed prefix and two_back is the prior prefix optimum; the two cases jointly cover every circularly valid plan.

Reuse it

When one wraparound edge breaks a linear DP, condition on excluding either endpoint, solve the resulting linear instances, and combine their optima.

Pattern: Reduce a circle to two linear DP problems.

Simple idea: A valid answer cannot take both the first and last houses. Solve once without the last house and once without the first house. Keep the larger answer.

def house_robber_two(nums: list[int]) -> int:
   def rob(line: list[int]) -> int:
      two_back = one_back = 0
      for money in line:
         two_back, one_back = one_back, max(one_back, two_back + money)
      return one_back

   if len(nums) == 1:
      return nums[0]
   return max(rob(nums[:-1]), rob(nums[1:]))

Cost: $O(n)$ time and $O(n)$ space from the two slices. Index ranges can reduce extra space to $O(1)$.