House Robber

Difficulty: Medium

Problem

A row of houses, each holding loot nums[i]. Adjacent houses share a linked alarm — rob two neighbors and the police arrive. Choose which houses to rob so that no two robbed houses are adjacent and the total loot is as large as possible. DP Foundations concept 7 previewed this exact street; now you build the full arc yourself — your first DECISION DP.

Example

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob houses 0, 2, and 4: 2 + 9 + 1 = 12. No two of them are adjacent, and no legal plan beats it — grabbing the tempting 7 caps you at 10.

Brute-force approach

The naive try-everything recursion is Step 1 of the guided walkthrough — this lesson walks the full arc from O(2^n) recursion to the O(1)-space table in one place.

Optimal approach

Key insight: At every house one question: rob it (plus the best two back) or skip it (best one back). The table answers it n times and the street is solved.

Classic 1D decision DP: at each house take max(skip, rob) using the best answers one and two houses back, filled left to right, then rolled into two variables for O(1) space.

Steps

1. STATE: dp[i] = max loot from houses 0..i, whether or not house i is robbed
2. TRANSITION: dp[i] = max(dp[i−1], dp[i−2] + nums[i]) — skip vs rob
3. BASE: an empty street is worth 0, so start prev2 = prev1 = 0
4. Fill left to right — each house costs one max() call
5. Only two lookbacks are ever alive → roll them in two variables for O(1) space

Time complexity: O(n) · Space complexity: O(1) with rolling variables