DP: house robber

You're a (strictly fictional, legally distinct) burglar working a street of houses lined up in a row. Each house has some stash of cash. There's one catch: the houses are wired together, so robbing two adjacent houses on the same night trips the alarm. Your goal is the maximum total you can grab without ever hitting two neighbours.

The dynamic programming insight: stand in front of house i and ask a single yes/no question — do I rob it or skip it?

• If you rob house i, you take its cash but you must have skipped house i - 1, so you add to the best you could do up to house i - 2.
• If you skip house i, your best is whatever you already had at house i - 1.

So the answer for each house is just the better of those two choices:

best[i] = max(best[i - 1], best[i - 2] + nums[i])

You never need the whole best array at once — only the previous two values. Roll two running totals forward and you're done in one pass, O(1) space.

Your task

Write rob(nums) that returns the maximum amount you can rob without taking from two adjacent houses. An empty street earns 0.

rob([1, 2, 3, 1])     # 4   -> rob houses 0 and 2 (1 + 3)
rob([2, 7, 9, 3, 1])  # 12  -> rob houses 0, 2, 4 (2 + 9 + 1)
rob([])               # 0
rob([5])              # 5
rob([2, 1, 1, 2])     # 4   -> rob houses 0 and 3 (2 + 2)

Hint: keep prev (best up to two houses back) and cur (best up to the last house). For each value, the new cur is max(cur, prev + value).