House Robber

House Robber: houses along a street hold nums[i] money each. Robbing two adjacent houses sets off an alarm. Return the most money you can rob without robbing two neighbours.

Example: [2, 7, 9, 3, 1] returns 12: houses 0, 2 and 4 (2 + 9 + 1).

At each house, recurse twice: once skipping it, once robbing it and jumping two houses ahead. That explores every valid plan — O(2ⁿ) — and solves the same suffix of the street over and over. The repeated subproblems are the sign that dynamic programming applies.

Let dp[i] be the most money from the first i houses. For the last of them, house i - 1, there are only two options:

1. Skip it: the best is whatever the first i - 1 houses gave — dp[i - 1].
2. Rob it: its neighbour is off-limits, so add nums[i - 1] to the best of the first i - 2 houses — dp[i - 2] + nums[i - 1].

So dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]), starting from dp[0] = 0 and dp[1] = nums[0]. Fill the table left to right; dp[n] is the answer. Each cell reads only the two before it, which is why two variables are enough in the optimised version.

The houses run along the top and the dp table under them. For each house, the two cells the choice reads — dp[i − 1] to skip and dp[i − 2] to rob — are marked, and the winner fills dp[i]. The last step walks the table backwards to light up the houses the best plan robs.

Each dp[i] reads only dp[i − 1] and dp[i − 2], so the table can shrink to two variables:

def rob(nums):
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

Same O(n) time, O(1) space. The table version is easier to trace — and to reconstruct which houses were robbed — which is why the walkthrough uses it.