Free Dynamic programming lessonsDynamic programming · Stage 5 · Knapsack · Step 3

Fewest pieces, not the most value

Same unbounded, forward-counting table, but minimising a count instead of maximising a value. About 12 minutes.

The fewest coins for any amount

A vending machine owes you 11 rupees in change and has plenty of 1, 2 and 5 rupee coins. What's the fewest coins it can hand over?

Think of it as the unbounded bag again, with a twist. Each coin is an item you can use as often as you like, and every coin costs you one. So for every amount, ask: which coin could have been the last one handed over? That coin, plus the fewest coins for what was left before it.

Try each coin as the last one: then add the best for what's left.

Some amounts can't be made at all

Start every amount at "impossible" (think infinity), except 0, which takes no coins at all. Then fill amounts from small to big. Any real count beats infinity, so the first way you find replaces it.

If an amount is still infinity at the end, no mix of coins makes it, and the answer is −1. For 11 with coins 1, 2 and 5, the answer is 3: 5 + 5 + 1.

Still infinity? then that amount can't be made: −1.

In code

INF = float("inf")
fewest = [0] + [INF] * amount
# INF: this amount can't be made

coins = [3, 4, 7], amount = 10 · fewest coins for each amount

012345678910

fewest

∞

Making 0 takes no coins. Every other amount starts at ∞, meaning 'no way found yet'.

Move 1 of 6

Quick check

Coins are 1 and 5. Making 4 takes four 1s. How few coins can make 5?

Show the answer

1. A single 5 coin, on top of 0 coins for nothing left over.

Your problem

Fewest coins

You get coins, a list of coin values, and a target amount. You have an unlimited supply of each coin. Return the fewest coins that add up to exactly amount, or −1 if no combination does.

Example

coins = [1, 2, 5], amount = 11 → 3

1 ≤ coins.length ≤ 100 · 1 ≤ coins[i] ≤ 10,000 · 0 ≤ amount ≤ 10,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.