#198MediumDynamic programming

House Robber

The tell: Maximise a sum with an adjacency restriction — a decision at each position.

How you get there

1At each house choose: rob it and add the best from two back, or skip it.
2best(i) = max(best(i-1), best(i-2) + value[i]).
3Only two previous values matter, so it collapses to O(1) space.

Solution

Python

def rob(nums: list[int]) -> int:
    prev2 = prev1 = 0
    for value in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + value)
    return prev1

Time: O(n)
Space: O(1)

What goes wrong

Assuming the answer alternates houses is wrong — [2, 1, 1, 2] shows why.

Test yourself on DSA Next: Longest Increasing Subsequence →