DSA AnimatorDSA animations
House Robber LC #198 Medium DP
Problem

Rob houses on a street. Adjacent houses have connected alarms — can't rob two adjacent houses. Return the maximum money you can rob.

Example
[2,7,9,3,1] → 12 (rob 2, 9, 1)
Constraints: 1 ≤ nums.length ≤ 100, 0 ≤ nums[i] ≤ 400
Try Examples
Custom:
Approach
dp[i] = max money from houses 0..i
At each house: Rob = nums[i] + dp[i-2] or Skip = dp[i-1]. Take max.
Houses & DP Values
Load an example.
Variables
house i
—
rob
—
skip
—
max loot
—
Step Logic
Press ▶ Play or Next Step to begin.
💰
Ready
0 / 0
Select an example and press Play.
Algorithm
1
prev2=0, prev1=0 (money from 0 houses ago, 1 house ago)
2
curr = max(prev1, prev2 + nums[i])
3
prev2=prev1, prev1=curr; return prev1
Time
O(n)
Space
O(1)
Why This Works

At each house, decide: Rob (get nums[i] + best from 2 houses ago) or Skip (keep best from previous). Two variables suffice since we only need the previous two dp values.

How to solve House Robber

LeetCode 198 · Medium · Dynamic Programming · Pattern: 1D DP

Why the obvious approach is slow

Trying every set of non-adjacent houses means about 2 to the power n choices. And simply taking every other house isn't reliable, because sometimes the best plan skips two houses in a row.

The key idea

At each house, you have exactly two choices. Rob it, and add its money to the best total from two houses back. Or skip it, and keep the best total from the house before. The best at each house is the larger of the two, and you only ever need the last two totals.

Remember

Best at i is the larger of skipping house i, or robbing it plus the best at i minus 2. Only the last two answers matter, so two variables are enough.

Run the animation above on your own input, or watch the 1:49 video explanation of House Robber with a dry run and Java code.

More Dynamic Programming problems