Coin Change

The problem

You are given coin values in coins and a target amount. You may use each value as many times as you like. Return the smallest number of coins that add up to exactly amount, or -1 if no combination does. An amount of 0 needs no coins, so its answer is 0. The values are all different and come in no particular order, and coins may be empty.

What to write

function solve(coins: number[], amount: number): number

Input
coins = [1,2,5]
amount = 11

Output
3

Input
coins = [2]
amount = 3

Output
-1

Constraints

Distinct positive coin values; 0–1,000 amount; at most 30 denominations.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Taking the largest coin first is tempting, but the coin values can be anything. With coins 1, 3 and 4, the amount 6 is best made as 3 + 3, while largest first gives 4 + 1 + 1. So every coin has to be considered, and the amount is at most 1,000, which keeps that affordable.

2. Hint 2: Ask a smaller question

   Make 11 from the coins 1, 2 and 5. Whatever the best combination is, some coin went in last. Suppose it was a 5. What amount did the other coins make, and how many coins would you want those to be?

3. Hint 3: Name the pattern

   Whichever coin goes in last, the coins before it must be a best answer for a smaller amount. So each amount up to amount has one best count, built from smaller amounts. One stored answer per total, built by adding one item at a time, is knapsack dynamic programming. The signal: items to choose and an exact total. Read the lesson on knapsack dynamic programming.

4. Hint 4: State the invariant

   The table has one slot for every amount from 0 to amount. A slot holds the fewest coins that add up to exactly that amount, or a mark that says no combination does. When a slot is being filled, the slots of all smaller amounts are already final.

5. Hint 5: Sketch the pseudocode

   table[0] = 0 and every other slot = infinity. For a from 1 to amount: for each coin that is not larger than a: table[a] = the smaller of table[a] and table[a - coin] + 1. Return table[amount], or -1 if it is still infinity.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Build minimum coin counts for increasing subtotals. Try each coin as the final coin and leave unreachable subtotals at infinity.

The slow way

Try each coin as the next coin, then do the same again for what is left, and keep the smallest count that reaches exactly 0. It is correct, but the same leftover amounts are worked out over and over. For amount 11 with coins 1, 2 and 5 that takes 527 calls, and for amount 30 more than 13 million.

The insight

Look at the last coin of a best combination. The coins before it must be a best combination for the amount that is left, because a better one there would improve the whole. So the answer for an amount is 1 plus the answer for some smaller amount, and each smaller amount has to be solved only once.

Step by step

1. Give every amount from 0 to the full amount a slot marked unreachable. A slot will hold the fewest coins that add up to exactly its amount. The mark is infinity, which is larger than any real count, so the first real count found replaces it.
2. Amount 0 takes no coins, so its slot is 0. This is the one answer known before any work is done. Every other count is built up from it, one coin at a time.
3. Fill in the slots in order, from amount 1 up to the full amount. A slot is worked out from the slots of smaller amounts. Going upward means those are already final when they are read.
4. Try each coin that is not larger than this amount as its last coin. Some coin has to go in last, and you cannot know which, so each coin gets a turn. A coin larger than the amount would overshoot it.
5. Keep the fewest: 1 for this coin plus the slot of what is left. With the last coin fixed, the coins before it should be as few as possible, and that count is already in the table. Infinity plus 1 is still infinity, so an unreachable rest stays unreachable.
6. Return the slot of the full amount, or -1 if it is still unreachable. A slot that never received a real count means that no combination adds up to the amount, and the problem asks for -1 in that case.

The same numbered steps are the comments in each solution.

function solve(coins, amount) {
  // 1. Give every amount from 0 to the full amount a slot marked unreachable
  const dp = Array(amount + 1).fill(Infinity);
  // 2. Amount 0 takes no coins, so its slot is 0
  dp[0] = 0;
  // 3. Fill in the slots in order, from amount 1 up to the full amount
  for (let a = 1; a <= amount; a++) {
    // 4. Try each coin that is not larger than this amount as its last coin
    for (const c of coins) {
      if (c <= a) {
        // 5. Keep the fewest: 1 for this coin plus the slot of what is left
        dp[a] = Math.min(dp[a], dp[a - c] + 1);
      }
    }
  }
  // 6. Return the slot of the full amount, or -1 if it is still unreachable
  return dp[amount] === Infinity ? -1 : dp[amount];
}

function solve(coins: number[], amount: number): number {
  // 1. Give every amount from 0 to the full amount a slot marked unreachable
  const dp = Array(amount + 1).fill(Infinity);
  // 2. Amount 0 takes no coins, so its slot is 0
  dp[0] = 0;
  // 3. Fill in the slots in order, from amount 1 up to the full amount
  for (let a = 1; a <= amount; a++) {
    // 4. Try each coin that is not larger than this amount as its last coin
    for (const c of coins) {
      if (c <= a) {
        // 5. Keep the fewest: 1 for this coin plus the slot of what is left
        dp[a] = Math.min(dp[a], dp[a - c] + 1);
      }
    }
  }
  // 6. Return the slot of the full amount, or -1 if it is still unreachable
  return dp[amount] === Infinity ? -1 : dp[amount];
}

def solve(coins, amount):
    # 1. Give every amount from 0 to the full amount a slot marked unreachable
    dp = [float("inf")] * (amount + 1)
    # 2. Amount 0 takes no coins, so its slot is 0
    dp[0] = 0
    # 3. Fill in the slots in order, from amount 1 up to the full amount
    for total in range(1, amount + 1):
        # 4. Try each coin that is not larger than this amount as its last coin
        for coin in coins:
            if coin <= total:
                # 5. Keep the fewest: 1 for this coin plus the slot of what is left
                dp[total] = min(dp[total], dp[total - coin] + 1)
    # 6. Return the slot of the full amount, or -1 if it is still unreachable
    return -1 if dp[amount] == float("inf") else dp[amount]

Example 1, traced

Input
coins = [1,2,5]
amount = 11

Output
3

Why it works

Each slot ends up holding the fewest coins that add up to exactly its amount, or stays unreachable if no coins do. Any way to make that amount ends with some coin, and before that coin comes a smaller amount whose best count is already in the table. Trying every coin as the last one and keeping the smallest total therefore misses nothing.

Time and space

Time O(amount × coin count), extra space O(amount). The table has one slot for each amount from 0 to amount, which is the O(amount) space. Filling a slot tries every coin once, so the time is the amount times the number of coins.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Taking the largest coin first. With coins 5, 10, 13, 12, 14 and amount 34, that takes 14 twice and a 5, is stuck with 1 left over, and returns -1. But 10 + 12 + 12 is 34.
• Using -1 as the unreachable mark and letting any count replace it. Adding 1 to -1 gives 0, which looks like the best count there is. For the single coin 2 and amount 3 that returns 0 instead of -1.
• Filling the table with 0 at the start. The smaller of 0 and any count is 0, so no slot ever changes and every answer is 0.

Pattern

Knapsack dynamic programming. Builds on Climbing Stairs and Min Cost Climbing Stairs.

Keep going