How Dynamic Programming Works

Dynamic programming keeps a table of answers to small sub-problems and reuses them to solve bigger ones. This example uses the fewest-coins problem with coins 1, 3, and 4: it fills in a table starting from amount 0, recording the fewest coins needed for each amount along the way. Because it reuses the already-computed answers for smaller amounts, unlike greedy, it always arrives at the optimal answer.