Coin Change

Dynamic programming · Build the best answer for every smaller amount · Stretch · about 28 min

Why it matters

It introduces bottom-up DP tables without a hidden trick.

How it connects

House Robber had two immediate past states. Coin Change asks every coin for a path to a smaller amount.

Try first

If you choose coin c last, which smaller amount must already be solved?

Interview cue

Every state reuses a solved smaller amount, so the table turns repeated search into lookup.