House Robber

L8 Hard Dynamic Programming

Concept

At any house you choose between "rob here (plus the two-back best)" and "skip here (keep the one-back best)" — a two-variable DP.

Houses in a row hold cash amounts in nums. You cannot rob two adjacent houses in the same night. Return the maximum you can collect.

Examples

▸ nums = [1, 2, 3, 1]

→ 4

▸ nums = [2, 7, 9, 3, 1]

→ 12

▸ nums = [5]

→ 5

Progressive Hints

Hint 1 · Nudge

At each house, choose between robbing it, adding the loot from two back, or skipping it and keeping the loot from one back.

Hint 2 · Plan

Track the best loot achievable up to the previous house and the one before that. For each new value, the best is the larger of those two choices, then slide the window forward.

Hint 3 · Approach

twoBack = 0, oneBack = 0. For each n: cur = max(oneBack, twoBack + n); twoBack = oneBack; oneBack = cur. Return oneBack.

Output

// Run your code to see the output here.