House Robber Problem, in depth: the two-state machine, reconstruction, circular, gap, tree and max-plus segment tree variants

The problem as a state machine

Walk the houses left to right. After deciding about house i, the only fact about the past that the future cares about is whether house i was robbed. The amounts in earlier houses no longer matter except through the best total they produced. So define two numbers after each house: take, the best total over houses 0..i given that house i was robbed, and skip, the best total given that it was not.

There are exactly three legal transitions. From SKIP you may rob the next house, landing in TAKE with the total increased by its value. From either state you may pass the next house, landing in SKIP with the better of the two totals. The missing edge, TAKE to TAKE, is the adjacency constraint. Writing the machine down before writing the code is what protects you later: when a variant changes the rules, you change an edge, not a tangle of indices.

Optimal substructure holds because the best plan ending in a given state must use the best plan for the previous house in whichever state it came from; any worse prefix could be swapped for the better one without breaking the constraint. That is the whole correctness argument.

From machine to a two-variable loop

Turning the machine into code takes one loop and two variables. The simultaneous assignment matters: both new values must be computed from the old pair, so update them together or use temporaries.

def rob(nums):
    take, skip = 0, 0          # best total if the last house was robbed / not robbed
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)

rob([2, 7, 9, 3, 1])           # 12  (2 + 9 + 1)
rob([])                        # 0

This is O(n) time and O(1) space. The textbook form dp[i] = max(dp[i-1], dp[i-2] + nums[i]) is the same machine with the states folded together: dp[i-1] equals max(take, skip) and dp[i-2] is the old skip value. Both are correct; the two-state form generalises more cleanly, because the state names say what they mean.

Initial values deserve a sentence. Before any house, nothing has been robbed, so skip is 0. Take is also set to 0 here, which is harmless because take only feeds skip through a max and all values are non-negative. If negative values were allowed you would initialise take to negative infinity, or simply note that a negative house is never worth robbing.

Reconstructing which houses to rob

Interview answers stop at the number; real systems need the plan. Reconstruction needs the full table (or a choice bit per house), because the two-variable loop throws history away. Keep best[i], the optimum over the first i houses, then walk backwards: if best[i] == best[i-1] house i-1 was skipped, otherwise it was robbed and you jump two places.

def rob_plan(nums):
    n = len(nums)
    best = [0] * (n + 1)       # best[i] = best total using houses 0..i-1
    for i in range(1, n + 1):
        best[i] = max(best[i - 1], (best[i - 2] if i >= 2 else 0) + nums[i - 1])
    plan, i = [], n
    while i >= 1:
        if best[i] == best[i - 1]:
            i -= 1             # house i-1 skipped
        else:
            plan.append(i - 1) # house i-1 robbed, so i-2 cannot be
            i -= 2
    return best[n], plan[::-1]

rob_plan([6, 1, 2, 7, 5, 3, 8])   # (21, [0, 3, 6])

Ties are broken towards skipping, which yields one optimal plan, not all of them. If you need the lexicographically smallest set of indices, or the plan with the fewest houses, encode that preference as a secondary key in the comparison rather than hoping the tie-break happens to match.

Worked example and why greedy fails

Trace the machine on houses 6, 1, 2, 7, 5, 3, 8, the row shown in the diagram. After house 0 the pair (take, skip) is (6, 0). House 1, worth 1: take becomes 0 + 1 = 1, skip becomes max(6, 0) = 6. House 2: take = 6 + 2 = 8, skip = 6. House 3, worth 7: take = 6 + 7 = 13, skip = max(8, 6) = 8. House 4: take = 8 + 5 = 13, skip = 13. House 5: take = 13 + 3 = 16, skip = 13. House 6, worth 8: take = 13 + 8 = 21, skip = 16. The answer is 21.

Notice what greedy would have done. Taking the largest house first picks 8, then 7, then 6 here and happens to win, but on 2, 3, 2 greedy takes 3 and gets 3 while the optimum is 4, and on 5, 6, 5 greedy gets 6 against an optimum of 10. The DP never commits early: at every step it carries both futures forward and lets the next value decide.

Circular rows: break the cycle by cases

In the circular variant the houses form a ring, so the first and last houses are neighbours. The state machine itself does not change; what changes is that the decision about house 0 constrains house n-1. The standard fix is case analysis on that one coupling: either house 0 is not robbed, so solve the line 1..n-1, or house n-1 is not robbed, so solve the line 0..n-2. Every valid plan falls into at least one case, and each case is an ordinary line.

def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]         # one house is not its own neighbour
    return max(rob(nums[:-1]), rob(nums[1:]))

The single-house guard is the classic bug: without it both slices are empty and the function returns 0. The same idea, breaking a cycle by fixing the state of one element and running the line algorithm per case, works for any cyclic DP whose coupling is a single edge. In machine terms you run the line machine once per allowed start state and reject end states that conflict with it.

A minimum gap of k houses

Suppose robbed houses must be at least k + 1 apart, so k houses between any two robbed ones (k = 1 is the original problem). The state is now how many houses ago you last robbed, capped at k + 1, so the machine has k + 2 states. In table form it collapses to one recurrence that looks back k + 1 places.

def rob_gap(nums, k):
    best = [0] * (len(nums) + 1)          # best[i] over houses 0..i-1
    for i in range(1, len(nums) + 1):
        prev = best[i - k - 1] if i - k - 1 >= 0 else 0
        best[i] = max(best[i - 1], prev + nums[i - 1])
    return best[-1]

Space can be cut to O(k) with a ring buffer of the last k + 1 values. The related stock-trading problems with a cooldown are the same machine with states named hold, sold and rest; recognising that they share a skeleton with House Robber turns a family of puzzles into one technique.

Houses on a tree

In the tree variant each house is a node of a binary tree and a node cannot be robbed together with its parent. The machine is the same, but it runs bottom-up over the tree instead of left to right. Each node returns its (take, skip) pair: robbing the node forces both children into skip, while skipping it lets each child pick its own better state independently.

def rob_tree(root):
    def go(node):              # returns (best if node robbed, best if node skipped)
        if node is None:
            return 0, 0
        lt, ls = go(node.left)
        rt, rs = go(node.right)
        return node.val + ls + rs, max(lt, ls) + max(rt, rs)
    return max(go(root))

This is O(n) and returns a pair rather than a single number, which is what removes the exponential blow-up of the naive recursion that recomputes grandchildren. For deep, unbalanced trees, Python recursion will hit its limit around a thousand levels; convert to an explicit post-order stack in production. The same pattern solves maximum-weight independent set on any tree, and the pair generalises to a vector when a node has more states.

Online updates with a max-plus segment tree

Now suppose the array changes: house values are updated online and you must answer the best total after each update. Re-running the loop costs O(n) per query. The state-machine view gives an O(log n) structure. Each house is a linear map on the state vector (take, skip) in the max-plus semiring, where addition is max and multiplication is +. House x maps (t, s) to (s + x, max(t, s)), which is the 2x2 max-plus matrix with rows (minus infinity, x) and (0, 0). The whole row is the product of those matrices, so a segment tree that stores products of ranges answers queries at the root and handles a point update by recomputing O(log n) 2x2 products.

NEG = float("-inf")

def mp_mul(a, b):              # max-plus product of 2x2 matrices
    return [[max(a[i][0] + b[0][j], a[i][1] + b[1][j]) for j in range(2)]
            for i in range(2)]

def house(x):                  # (take, skip) -> (skip + x, max(take, skip))
    return [[NEG, x], [0, 0]]

class RobberTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.t = [None] * (4 * self.n)
        self._build(1, 0, self.n - 1, nums)

    def _build(self, v, lo, hi, nums):
        if lo == hi:
            self.t[v] = house(nums[lo]); return
        mid = (lo + hi) // 2
        self._build(2 * v, lo, mid, nums)
        self._build(2 * v + 1, mid + 1, hi, nums)
        self.t[v] = mp_mul(self.t[2 * v + 1], self.t[2 * v])   # right applied after left

    def update(self, i, x, v=1, lo=0, hi=None):
        hi = self.n - 1 if hi is None else hi
        if lo == hi:
            self.t[v] = house(x); return
        mid = (lo + hi) // 2
        if i <= mid:
            self.update(i, x, 2 * v, lo, mid)
        else:
            self.update(i, x, 2 * v + 1, mid + 1, hi)
        self.t[v] = mp_mul(self.t[2 * v + 1], self.t[2 * v])

    def best(self):            # start state: nothing robbed, (take, skip) = (-inf, 0)
        m = self.t[1]
        return max(m[0][1], m[1][1])

The one trap is order. Matrix products are not commutative, and because the state vector is a column the later houses must sit on the left of the product: a node stores right-child times left-child. Swap them and the structure still returns plausible numbers, which is why this code was tested against the plain loop after every random update. Range queries work the same way by multiplying the O(log n) covering nodes in order.

Failure modes

• Updating take and skip in sequence. Writing take = skip + x and then skip = max(take, skip) uses the new take and lets you rob adjacent houses. Use simultaneous assignment or a temporary.
• Circular input with one house. Both slices are empty, the answer comes back 0 instead of the single value.
• Negative values. The problem assumes non-negative amounts. With negatives, zero initialisation still gives the right answer for the line because skipping is always allowed, but the max-plus tree must start take at minus infinity, as the code does.
• Overflow in fixed-width languages. Sums of n values can exceed 32 bits; use 64-bit totals in Java, C++ or Go.
• Naive tree recursion. Recursing on rob-this-node versus rob-grandchildren without returning pairs revisits subtrees exponentially often.
• Wrong product order in the segment tree. Silent wrong answers; always fuzz against the O(n) loop.

Choosing a variant

What to do next

1. Implement the two-variable loop from memory, then break it on purpose by updating the variables one at a time and watch a brute-force test catch it.
2. Write a brute-force checker over all subsets for n up to 12 and keep it next to every variant you write.
3. Add reconstruction and decide explicitly how ties should break for your use case.
4. Solve the circular and tree variants by drawing the machine first, then coding the edges.
5. Build the max-plus segment tree, fuzz it with random updates, and then try a range query version.
6. Keep learning: dynamic programming in depth, filling DP tables cell by cell, the knapsack family, coin change and loop order and segment trees.