Dynamic Programming — House Robber

Houses stand in a row; money[i] is what house i holds. Robbing **two
adjacent houses sets off the alarm. Return the most money** you can take.

Greedy fails ([2, 1, 1, 2]: take both ends for 4, not the "every other
house" 3). At each house the choice is: skip it and keep the best up to the
previous house, or rob it and add it to the best up to the house before that:

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

Only the last two values are ever needed, so O(n) time and O(1) space.

Examples

solve([1, 2, 3, 1])     → 4    // houses 0 and 2
solve([2, 7, 9, 3, 1])  → 12   // houses 0, 2 and 4
solve([2, 1, 1, 2])     → 4    // houses 0 and 3

Constraints

• 0 <= money.length <= 100000, 0 <= money[i] <= 400