Dynamic programming · Unbounded knapsack

Medium · O(amount × n) time · O(amount) space

Problem

You are given an integer array coins with the coin values, and an integer amount. You have an unlimited supply of each coin. Return the fewest coins that add up to exactly amount. If no combination works, return -1.
Example 1 Input: coins = [1, 2, 5], amount = 11 Output: 3 (5 + 5 + 1) Example 2 Input: coins = [2], amount = 3 Output: -1 (2s can never make an odd amount)
Constraints 1 ≤ coins.length ≤ 12 1 ≤ coins[i] ≤ 2^31 − 1 0 ≤ amount ≤ 10^4

Brute force

Picture a shop till. You have an endless supply of coins of a few values, and you must pay exactly a given amount using as few coins as you can. If the amount cannot be paid exactly, the answer is -1.

The rules, in three steps:

  1. The coins must add up to the amount exactly, not close to it.
  2. You can use each coin value as many times as you like.
  3. Return the smallest number of coins, or -1 if it is impossible.

A natural first idea is greedy: always take the biggest coin that still fits. It feels right, so test it. Take coins [1, 3, 4] and the amount 6.

Greedy takes the 4 first, then is stuck with 2 left, so it pays 1 + 1. That is three coins in total. But 3 + 3 does it with two coins, and never uses the biggest coin. So greedy is not safe, and we need something that really checks the choices.

The honest way to check every choice: try each coin as the last coin you hand over, and solve what is left by the same method.

The problem with it

Every call splits into one call per coin, and the calls go as deep as the amount. That is a huge number of calls, far too many for an amount like 10,000.

It also repeats itself. Paying 3 then 1 and paying 1 then 3 both leave the same remainder of 2, and the code solves "what is the best way to pay 2?" again each time.

How to think your way to the optimal solution

Look at the part we keep repeating: "the fewest coins to pay this smaller amount". If we worked that out once for every amount from 0 up to the target and wrote the answers in a table, we could simply look them up. So what is the best answer for each smaller amount, and how does each one use the ones before it?

Take any way of paying amount a. It ends with some last coin c. Take that coin away, and the rest pays a − c. That rest must itself be a best way to pay a − c. If it were not, we could swap in a better one and beat our own answer. So the best way to pay a is always one coin on top of the best way to pay a smaller amount.

We do not know which coin is last, so we try every coin c that is not bigger than a, and keep the smallest result. Write dp[a] for the fewest coins that pay a:

The optimal solution

  1. Set dp[0] = 0 and every other cell to the huge value.
  2. For each amount a from 1 up to the target, try every coin c.
  3. c is bigger than a⟶skip it, the coin does not fit
  4. c fits⟶dp[a] = min(dp[a], dp[a − c] + 1)
  5. Return dp[amount], or -1 if it is still the huge value.

By hand, with coins [1, 3, 4] and amount 6:

  1. dp[0] = 0. Paying nothing takes no coins.
  2. dp[1] = 1. Only coin 1 fits. It leaves 0, so 1 + 0 = 1.
  3. dp[2] = 2. Only coin 1 fits. It leaves 1, so 1 + 1 = 2.
  4. dp[3] = 1. Coin 1 would give 1 + dp[2] = 3. Coin 3 gives 1 + dp[0] = 1. The smaller wins.
  5. dp[4] = 1. Coin 4 leaves 0, so the answer is 1.
  6. dp[5] = 2. Coin 1 gives 1 + dp[4] = 2, coin 3 gives 1 + dp[2] = 3, coin 4 gives 1 + dp[1] = 2. The best is 2.
  7. dp[6] = 2. Coin 1 gives 3, coin 3 gives 1 + dp[3] = 2, coin 4 gives 1 + dp[2] = 3. The best is 2: it is 3 + 3, the answer greedy missed.

Press Play, or use the arrow keys, to watch the table fill. The first input is this same example. Watch dp[3] and dp[6]. The order of the two loops does not matter here, because each cell reads only smaller amounts that are already final.

Complexity analysis

O(A × n)
Time. Here's why: A is the amount and n is the number of coin values. The table has A cells, and for each cell we try n coins. Trying one coin is a single comparison, so it takes the same small time each time.
O(A)
Space. One list of A + 1 numbers. Nothing else is stored, and the answer is one number.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Now count how many different ways there are to make the amount, instead of the fewest coins."

What they are checkingWhether you understand why the order of the two loops matters. Counting is a close cousin of this problem, and the loop order is where most people slip.

A strong answerI swap min for adding, and set dp[0] = 1, since there is one way to pay nothing. The important change: the coin loop goes on the outside and the amount loop on the inside. Then each coin is "used up" in turn, so 1 + 2 and 2 + 1 count as one way. With the amount loop on the outside, they would be counted as two different orders.

"Return the coins you used, not only how many."

What they are checkingWhether you can carry an answer along with a number. This is a very common follow-up for table-filling problems.

A strong answerNext to dp I keep a second list, pick[a], holding the last coin that gave the best value for amount a. At the end I start at the target, write down pick[amount], subtract it, and repeat until I reach 0. That costs only as many steps as there are coins in the answer.

"The amount can be a billion, but there are only three coin values. Does your table still work?"

What they are checkingWhether you notice that the table size depends on the amount, and whether you can say what changes when the limits change.

A strong answerNo. A table with a billion cells is too big for memory and too slow to fill. With only a few coin values, the question becomes a number puzzle instead: I would look at the structure of the coin values, for example how large coins can be repeated and then fixed up with the small ones. I would not guess a formula in the interview. I would say the table does not scale and ask for the exact limits first.

Spot this pattern