Dynamic Programming
coins 1, 3, 4 — fewest needed to make each amount
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| coins | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
How few coins from {1, 3, 4} add up to 6? Build a table: one cell per amount from 0 up to 6. Amount 0 needs 0 coins — that's the one answer we get for free.
step 01/30
- comparing
- in final place
- found it