← DSA Atlas
Dedicated problem page · #198

House Robber

MediumOne-Dimensional Dynamic ProgrammingTake-or-skip linear DPDynamic programming with rolling variables
Solve on LeetCode ↗
198
MediumOne-Dimensional Dynamic ProgrammingDynamic programming with rolling variablesTake-or-skip linear DP

House Robber

Given an integer array nums where nums[i] is the money in the i-th house along a street, return the maximum amount you can rob. You cannot rob two adjacent houses, because adjacent houses share a connected alarm system that alerts the police.

Open official problem prompt ↗
In plain English

Compute the largest amount of money obtainable from a line of houses when picking any subset that contains no two neighbors.

Picture it like this

Walking down a street of vending machines you can only trigger every other one; at each machine you decide whether skipping it or grabbing it (plus whatever you banked before its neighbor) leaves you richer.

Example
Input
nums = [2, 7, 9, 3, 1]
Output
12
Why
Robbing houses 0, 2, and 4 gives 2 + 9 + 1 = 12, and no two are adjacent.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 400
Pattern lesson

See the pattern, then code

Take-or-skip linear DP
Recognition clue

You want a maximum sum over a linear array with a 'no two chosen elements are adjacent' rule -- the classic signal for take-or-skip DP.

↗
One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. At each house the best total is either the best up to the previous house (skip this one) or this house's money plus the best up to two houses back (take this one).

New words, made simpleKnow these before the algorithm
Adjacent constraint
Two elements at consecutive indices cannot both be chosen.
Rolling variables
Keeping only the last one or two DP results instead of a full table.
Optimal substructure
The best answer for a prefix is built from best answers of shorter prefixes.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Exhaustive subsets

Exponential; unusable beyond tiny inputs.

Enumerate every subset of houses and keep the max-sum valid one.

Time O(2^n)Space O(n)
Best choiceTake-or-skip DP (rolling)

Single linear pass with constant memory.

For each house keep max(skip previous best, take money + best two back).

Time O(n)Space O(1)
The rule we keep true

Invariant

After processing house i, curr holds the maximum robbable amount considering houses 0..i, and prev holds that maximum for houses 0..i-1.

Why this is correct

Reasoning

Any optimal plan either skips the last house (so its value equals the optimum of the shorter prefix, prev-side) or robs it (forcing house i-1 to be skipped, so it equals money[i] plus the optimum two houses back). Taking the max of these two exhaustive cases at every step yields the global optimum.

The algorithm in three movesSay these aloud before coding
1Track best-so-far excluding the previous house (prev) and best-so-far including it (curr)

after 9: prev=7, curr=11

2For each house compute max(curr, prev + money)

after 3: prev=11, curr=11

3Shift the two variables forward

after 1: curr=max(11,11+1)=12

4Return the final curr

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
71
92
33
14
1 · Readprev=0, curr=0
2 · AskInitialize both rolling states to zero.
3 · Update stateprev=0, curr=0
4 · ResultNo houses processed yet.
Key takeaway

The chosen non-adjacent houses 0, 2, and 4 sum to the optimal 12.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Two rolling accumulators

    prev = best excluding the previous house, curr = best including it; both start at 0 for an empty prefix.

  2. 2
    Lines 4-5Take-or-skip transition

    The tuple assignment advances prev to the old curr and sets curr to max(skip, prev+x) atomically so we never read a half-updated value.

  3. 3
    Lines 6Answer

    curr is the optimum over the whole array once the loop ends.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single house -- answer is that house's value
  • All zeros -- answer is 0
  • Two houses -- answer is the larger of the two
  • Large middle value that makes skipping both neighbors optimal
!

Common beginner mistakes

  • Assuming the answer alternates strictly (even indices vs odd) -- sometimes skipping two in a row is optimal
  • Forgetting to update prev before curr, which corrupts the recurrence
  • Initializing curr to nums[0] without handling the length-1 case cleanly
Check your understanding

Why is it not always optimal to just take every other house starting at index 0?

More in One-Dimensional Dynamic Programming

#322Coin ChangeUnbounded knapsack (min coins)#300Longest Increasing SubsequencePatience sorting (tails array)#5Longest Palindromic SubstringExpand around center#32Longest Valid ParenthesesIndex stack with sentinel base#70Climbing StairsFibonacci-style linear DP#91Decode WaysFibonacci-style linear DP