House robber
A row of houses holds money: [2, 7, 9, 3, 1]. Rob any set of houses, but never two adjacent ones. Maximize the haul.
Apply the lesson 9-1 discipline. Meaning: table[i] = the best haul considering only the first i houses. Recurrence, from the choice at house i (1-indexed):
- Skip it: you keep the best of the first i-1 houses,
table[i-1]. - Rob it: you take
houses[i-1]plus the best of the first i-2 (the neighbor is off-limits),table[i-2] + houses[i-1].
table[i] = max(table[i-1], table[i-2] + houses[i-1])
Base cases: table[0] = 0, table[1] = houses[0]. This choose-or-skip recurrence is the backbone of dozens of problems (stock cooldowns, deleting numbers, skipping exams). Learn the shape, not just the problem.
Code exercise · python
Run this. The printed table shows the running "best so far": watch entry 4 stay at 11 (robbing house 4 is not worth breaking 2+9) and entry 5 rise to 12 (2+9+1).
Quiz
In the recurrence table[i] = max(table[i-1], table[i-2] + houses[i-1]), why is the rob-option table[i-2] + money and not table[i-1] + money?
Code exercise · python
Your turn, the follow-up interviewers love: the street is a CIRCLE, so the first and last houses are also adjacent. Trick: the answer either skips the first house or skips the last, so run the straight-line rob (given) on houses[1:] and on houses[:-1] and take the max. Handle the single-house case separately.
Problem
Houses hold [5, 1, 1, 5] on a STRAIGHT street (no circle). What is the maximum non-adjacent haul?