House robber
Dynamic programming solves a big problem by building on answers to smaller ones, and remembering them. The best total from the first i houses is either the best from the first i − 1 (skip house i), or house i plus the best from the first i − 2 (take it). Fill those answers in from the left.
2793184
Take money from houses in a row, but never from two neighbours. What is the most you can take?
1function rob(houses) {2 const best = new Array(houses.length + 1).fill(0);3 for (let i = 1; i <= houses.length; i++) {4 const skip = best[i - 1];5 const take = (i >= 2 ? best[i - 2] : 0) + houses[i - 1];6 best[i] = Math.max(skip, take);7 }8 return best[houses.length];9}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | one pass, two lookups per house |
| average | n | any input |
| worst | n | trying every allowed set instead is exponential |
| space | n | the table; two variables are enough if you only need the total |
Where it breaks
- Greedy takes the wrong houses. Pick Greedy trap: grabbing the biggest house first takes the first 9, which blocks both 6s next to it, for 18 in all. The table finds 21 by taking 6, 6 and the last 9.
- Plain recursion repeats itself. Asking "take or skip" recursively without the table recomputes the same smaller answers over and over, and the work doubles with every house. The table computes each answer once.
- Getting the plan, not just the total. The table only stores totals. To see which houses to take, walk it backwards: where the total changed, that house was taken.