ChoralSoft Learn
Dynamic programming, one cell at a time
Why remembering small answers beats recomputing them.
Fewest coins, built up from small answers
With coins of 1, 3, 4, what is the fewest coins that make each amount? Each cell reuses the answers to its left, which is the heart of dynamic programming.
0:0
Zero amount needs zero coins. Press “Fill next cell”.
Cell “amount:coins”. Greedy choices can fail here; try 6 with coins 1, 3 and 4. Read when greedy is enough.