House Robber

House Robber is the gateway to one-dimensional dynamic programming. It teaches the core DP move: define a small "best so far" value for each position, then build each one from the answers you already computed.

The slow way first

The brute-force idea: try every valid subset of houses — every combination that never picks two neighbors — and keep the richest. There are exponentially many such subsets, so this is O(2ⁿ): hopeless for a long street.

The question to ask: standing at house i, what is the most I can carry away? It only depends on two earlier answers — the best up to the previous house, and the best up to the house two back. That overlap is exactly what dynamic programming exploits.

The idea: best up to each house

Define dp[i] = the most money robbable from houses 0..i. At house i you have two choices:

• Skip house i — then you keep whatever was best up to i-1, which is dp[i-1].
• Rob house i — then you cannot touch i-1, so you add nums[i] to the best up to i-2, which is dp[i-2] + nums[i].

Take the bigger of the two: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

The two base cases anchor the recurrence: dp[0] = nums[0] (one house, just rob it) and dp[1] = max(nums[0], nums[1]) (two adjacent houses, take the richer).

Walk through it

Step through the animation. The top row is nums; the bottom row is dp, filled left to right. For nums = [2, 7, 9, 3, 1]: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 2 + 9) = 11, dp[3] = max(11, 7 + 3) = 11, and dp[4] = max(11, 11 + 1) = 12. The pointer i highlights the two cells each new answer is built from. The final cell, dp[4] = 12, is the answer.

Pseudocode

if the street is empty, return 0
dp[0] = nums[0]                          # one house: rob it
if there are at least two houses:
    dp[1] = max(nums[0], nums[1])        # two adjacent: take the richer
for each house i from 2 onward:
    skip = dp[i-1]                       # do not rob house i
    rob  = dp[i-2] + nums[i]             # rob house i, add best up to i-2
    dp[i] = max(skip, rob)
return dp[last]                          # best over the whole street

The Python solution

def rob(nums):
    if not nums:
        return 0
    dp = [0] * len(nums)
    dp[0] = nums[0]
    if len(nums) > 1:
        dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[-1]

• The empty-street guard returns 0 so dp[-1] is always safe.
• dp[i] holds the most money robbable from houses 0..i.
• dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]) seed the two base cases.
• Lines 8 and 9 are the heart of the algorithm: each dp[i] is the larger of skipping (dp[i-1]) and robbing (dp[i-2] + nums[i]).
• dp[-1] is the best over the entire street, so we return it.

Complexity

We fill n cells, each in constant time, so the pass is O(n). The dp array costs O(n) space; since each dp[i] only needs the previous two values, you could shrink that to O(1) with two rolling variables — a common interview follow-up.

When this pattern shows up

Practice