House Robber

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    Problem statement

    A row of houses each holds some money (a non-negative integer). Choose houses to take money from so that no two chosen houses are next to each other, and return the largest total you can collect.

    The textbook first problem for one-dimensional dynamic programming: each house is a yes/no choice whose effect reaches exactly one step ahead. Interviewers like it because the greedy guesses look right and are wrong. Original problem: LeetCode 198.

    Example

    Houses 0, 3 and 5 are never neighbours and give 5 + 10 + 2 = 17, the best possible.
    Houses 0, 3 and 5 are never neighbours and give 5 + 10 + 2 = 17, the best possible.
    Input:  [5, 1, 2, 10, 6, 2]
    Output: 17          # houses 0, 3, 5: 5 + 10 + 2
    Input:  [2, 9]
    Output: 9

    Constraints (assumed)

    • 1 ≤ n ≤ 100,000 houses; 0 ≤ value ≤ 10,000.

    What this question tests

    • Defining a state ("best total using the first i houses") and a recurrence from a take/skip choice.
    • Seeing why greedy picks (largest first, every other house) fail.
    • Shrinking the table to O(1) space.

    Questions to ask first

    1. Can values be zero or negative? (Here: non-negative; with negatives you'd simply never take those houses.)
    2. Is the row a line or a circle? (Here: a line. The circle is a classic follow-up.)
    3. Do you want the total or the chosen houses? (Here: the total.)
    4. Can the list be empty? Return 0.