Solving the Coin Change Problem

It’s a quite common problem in real life: how to find the minimum number of coins, to pay a specific amount with coins of different denominations? When I first see this problem in Leetcode, it took me a while to figure it out. After learning more about dynamic programming, I found it’s easy to understand and solve this problem. In this post, I'll introduce the algorithm and code to solve this classic problem.

Problem description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

You can solve it online here: leetcode 322

Explanation

It seems too complicated to solve this problem. We need to consider all combinations of coins to get the minimum result. For example, with coins = [1, 2, 5], in order to get the amount 11, the following are the possible combinations:

• 1 * 11 = 11, cost 11 coins;
• 1 * 9 + 2 * 1, cost 10 coins;
• 1 * 7 + 2 * 2, cost 9 coins;
• 1 * 6 + 5 * 1, cost 7 coins;
• ……
• 1 * 1 + 5 * 2, cost 3 coins, is the minimum number of coins

To solve this problem, considering all the combinations, it’s best to utilize the dynamic programming algorithm to help record the result of different cases. Here, I’ll use an array to store the result.

First of all, let’s build an array of size amount + 1 to record the number of coins. From index 0 to index amount , each element is representing the minimum number of coins needed to form the index number. It’s clear that there’s no way to form the amount 0, so aray[0] = 0.

Assume the given coins are [1, 2, 5], the amount is 8, the initial array is:

arr = [0, inf, inf, inf, inf, inf, inf, inf, inf]

Let’s fill this array out by considering different cases:

• Case 1: build the amount with coin 1 only:

To determine the amount 1 forward, for each amount, we need to consider: can this amount can be built with one coin and the coin with the amount (amount-coin) ? Because this calculation will give me the minimum number of coins I need to build the current number.

After we consider all amounts range from 1 to 8, now the array is:

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]

• Case 2: build the amount with coin 1, and coin 2 only:

Based on the previous case, when introducing coin 2, we need to update the array to find the minimum number. Similar to case 1, when building each element in the array, we’ll find the minimum number between array[i], and array[i-coin] + 1.

After we consider all amounts range from 1 to 8, now the array looks like this:

arr = [0, 1, 1, 2, 2, 3, 3, 4, 4]

• Case 3: build the amount with coin 1, coin 2, and coin 5:

Now let’s introduce coin 5. When the amount is greater than 5, we might consider using it to replace some coins. For example, when the amount is 5, we can use 1 coin instead of 3 coins(2 * 2 coin+ 1 * 1 coin), thus we’ll update our array again to find the minimum number of coins.

After we consider all amounts range from 1 to 8, now the array looks like this:

arr = [0, 1, 1, 2, 2, 1, 2, 2, 3]

We’ve considered all the given coins, array[8] is the result we want, which means 3 coins are needed to form the amount 8.

Code

def coinChange(self, coins: List[int], amount: int) -> int:
    arr = [amount + 1] * (amount + 1)
    arr[0] = 0
        
    for coin in coins:
        for i in range(1, len(arr)):
            if coin <= i:
                arr[i] = min(arr[i], arr[i - coin] + 1)
        

    if arr[amount] > amount:
        return -1
    else:
        return arr[amount]

It takes O(n) extra space and O(m * n) running time: m is the number of coins, and n is the amount.