House Robber

Find the most money that can be taken without choosing neighboring houses.

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

Problem trace

House Robber: For each prefix of houses, keep the better of skipping the current house or taking it after the best prefix ending two houses earlier.

Input and goalFind the most money that can be taken without choosing neighboring houses.

Initialize before house 0For money [2, 7, 9, 3, 1], both saved prefix answers start at zero.

next i=0house 0: $20house 1: $71house 2: $92house 3: $33house 4: $14

statetwo_houses_back=0, one_house_back=0meaningbest totals before any house

Recognize it

Items lie in a line, adjacent choices conflict, and the objective asks for a maximum total rather than the exact chosen sequence.

Keep true

Before house i, one_house_back is the optimum for houses through i - 1 and two_houses_back is the optimum through i - 2. Therefore max(one_back, two_back + money[i]) is the complete optimum through i.

Reuse it

When choosing item i only conflicts with a fixed neighborhood, compare the optimum that excludes i with value[i] plus the last compatible optimum. This transfers to weighted independent sets on paths and cooldown scheduling.

Pattern: DP with two saved values.

State: Best answer one house back and two houses back.

Simple idea: At each house, choose the better result: skip it, or take it plus the best answer from two houses back.

def house_robber(nums: list[int]) -> int:
   two_houses_back = 0
   one_house_back = 0

   for money in nums:
      current = max(one_house_back, two_houses_back + money)
      two_houses_back, one_house_back = one_house_back, current

   return one_house_back

Cost: $O(n)$ time and $O(1)$ space.