Making change and dynamic programming
Lesson 8 of 11
8Making change and dynamic programming
The big pictureGreedy takes the biggest coin each time; it works with ordinary currency but fails with odd coins. Dynamic programming tries every possibility without repeating work, because it remembers.
What the picture shows: Building the table from smallest to largest. Each cell is computed once from cells before it.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
Imagine you know the fewest coins for every amount from 0 to 9. To make 10, try: use a 5 and 5 remains, whose answer you know; use a 1 and 9 remains, whose answer you know. Take the best and add one. That is how you build each amount from the ones before.
Fewest coins: dp[0] = 0, and dp[a] = 1 + min(dp[a - c]) over every coin c ≤ a that is reachable, else infinity. Time O(amount × coins), memory O(amount). Number of ways: ways[0] = 1, with the outer loop over coins and the inner over amounts so orderings (1+2 and 2+1) are not counted twice. Greedy is correct only for "canonical" systems like the riyal or the euro.
Before You Start
🔁Loops and lists
You write nested loops and update list items.
🧩Problem solving
The lesson on splitting a problem into smaller ones.
The Core Idea
1Greedy and when it fails
With coins 1, 3 and 4 and an amount of 6: greedy takes 4, then 1, then 1 = three coins, while the best is 3+3 = two coins.
def greedy(coins, amount):
used = []
for c in sorted(coins, reverse=True):
while amount >= c:
amount -= c
used.append(c)
return used if amount == 0 else None
print(greedy([1, 3, 4], 6))
print(greedy([1, 5, 10, 25], 30))2The number-of-ways table
This is the sibling form of the problem: in how many ways can you make the amount? ways[a] adds the ways ending with each coin. The outer loop over coins stops the same set being counted in another order.
def count_ways(coins, amount):
ways = [1] + [0] * amount
for c in coins:
for a in range(c, amount + 1):
ways[a] += ways[a - c]
return ways[amount]
print(count_ways([1, 2, 5], 5))
print(count_ways([2], 3))
print(count_ways([1, 5, 10, 25], 100))3Exercise: the fewest coins
Now apply the same idea to the other question. Start with dp = [0] + [inf] * amount, try every coin for each amount and take the min. If dp[amount] stays infinite the amount is impossible. Test on: coins [1, 3, 4] and amount 6 (answer 2), coins [2] and amount 3 (impossible), and amount 0 (answer 0).
Worked example
Problem: in how many ways can you make 4 with coins 1 and 2? Table: after coin 1: [1,1,1,1,1]. After coin 2: ways[2] = 1 + ways[0] = 2, ways[3] = 1 + ways[1] = 2, ways[4] = 1 + ways[2] = 3. Answer: 3 ways: 1+1+1+1, 1+1+2, 2+2.
Myth vs Reality
| Myth | Reality |
|---|---|
| Greedy always gives the best. | True only for coins like the riyal. With [1,3,4] it fails. |
| Dynamic programming means recursion. | It means saving answers to smaller problems. A table with loops is often simpler and faster. |
Where you meet it at work
🏧Cash machines
Deciding which notes to dispense for an amount.
🎒Knapsack problems
The same table idea for picking items under a weight limit.
Test your understanding
With coins 1, 3 and 4, how many coins does 6 need at best?
3+3. Greedy gives 4+1+1 and gets it wrong.
What is ways[0] in the number-of-ways table?
There is one way to make zero: take nothing.
What is the table solution's time?
Each amount cell is tried with each coin once.
Quick review cards
Check Your Understanding
When is an amount impossible?
When dp[amount] stays infinite after trying every coin.
Why start from small amounts?
Because each cell depends on smaller cells that must already be computed.
What separates the two questions?
Number of ways adds (+); fewest coins takes the minimum (min) and adds one.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Done with this lesson?
Sign in to save your progress.