House Robber

A row of houses, each holding some money. You want the largest haul, but the alarms are wired so you can never rob two houses that sit next to each other. Which houses do you take?

dp[i] = max(dp[i-1], dp[i-2]+nums[i])

At each house, take the better of two plans: skip this house, or rob it plus the best from two houses back.

See it build

houses = [2, 7, 9, 3, 1] → best haul 12 (rob houses 0, 2, 4).

The Problem

The choice is take it or leave it

In the last two problems, both routes into a stair were always allowed. Here you face a real decision at every house: rob it or skip it. Robbing a house forbids the one right before it, so the two choices lead to different pasts. Dynamic programming keeps the best total under each choice, so you never have to guess.

What dp[i] means, in words

dp[i] is the most money you can rob from the houses up to and including house i. The final answer is the value in the last cell.

First house (house 0)

With only one house in view, there is nothing to compare against. Rob it. So dp[0] = nums[0].

First two houses (house 1)

The two are adjacent, so you cannot take both. Rob whichever holds more. So dp[1] = max(nums[0], nums[1]).

The Key Idea

At each house, weigh two plans

Stand at house i. Plan one: skip it, and keep whatever was best up to the house before it. Plan two: rob it, adding its money to the best total from two houses back, since the house right before is now off limits. Keep the larger of the two plans. That is the whole solution.

skip house idp[i-1]

rob house idp[i-2] + nums[i]

→

keep the largerdp[i]

dp[i] = max( dp[i-1] , dp[i-2] + nums[i] )

Try It

Walk the street, house by house

Press play, or step through it. The top row is the money in each house. The bottom row is the best haul possible up to that house. Watch each house decide between skipping and robbing.

Press play to start walking the street

Press play or step forward to begin.

The amber ring marks the skip plan (best up to the previous house); the teal ring marks the rob plan (this house plus the best from two back).

The Result

The filled answer row

For this street, the recurrence produces the bottom row below. The last cell holds the best haul.

Best possible haul: 12, by robbing houses 0, 2, and 4.

The Code

Same idea, two implementations

The change from Min Cost Climbing Stairs is only the operator and what the two routes mean: min became max, and the routes became skip versus rob.

Complexity

What the optimization actually buys you

Array

TimeO(n)

SpaceO(n)

Two variables

TimeO(n)

SpaceO(1)

One pass down the street, a fixed amount of remembered state. The same profile as every 1D problem before it.

Pattern To Remember

When each item offers a take-it-or-leave-it choice, and taking one blocks a neighbor, track the best total under each choice.

dp[i] = max(skip: dp[i-1], take: dp[i-2] + value[i])

The same take-or-skip shape appears in House Robber II, Delete and Earn, and many subsequence problems. Next on the course: Unique Paths, where the strip grows into a two-dimensional grid.