House Robber
Houses along a street hold given amounts of money. Robbing two adjacent houses trips an alarm. Return the maximum amount you can steal without robbing two neighbours.
- 1 ≤ n ≤ 100
- 0 ≤ nums[i] ≤ 400
- Maximise with a no-two-adjacent constraint
- Decision at each house: take it (skip previous) or skip it
- Optimal substructure over a prefix
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Let best(i) be the maximum loot from the first i houses. Either skip house i (best(i - 1)) or rob it and add to the best of the first i - 2 (best(i - 2) + nums[i]). Take the maximum. Only the last two values are needed, so two rolling variables suffice.
- Greedy choices like "take every other house" fail on [2,1,1,2]. The circular variant runs the same DP twice, excluding the first or the last house.