This problem follows the Circular DP pattern, commonly found in the 1-D Dynamic Programming category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Run House Robber twice: once excluding first house, once excluding last. Take max.
Breaking the circle into two linear problems eliminates the circular constraint — at least one of the two ranges excludes both endpoints being robbed.
def rob_linear(houses):
prev2, prev1 = 0, 0
for h in houses:
prev2, prev1 = prev1, max(prev1, prev2 + h)
return prev1
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))Practice House Robber II and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.
Practice this problem