dynamic-programming Coin Changing Problem Number of Ways to Get Total

Example

Given coins of different denominations and a total, in how many ways can we combine these coins to get the total? Let's say we have coins = {1, 2, 3} and a total = 5, we can get the total in 5 ways:

• 1 1 1 1 1
• 1 1 1 2
• 1 1 3
• 1 2 2
• 2 3

The problem is closely related to knapsack problem. The only difference is we have unlimited supply of coins. We're going to use dynamic programming to solve this problem.

We'll use a 2D array dp[n][total + 1] where n is the number of different denominations of coins that we have. For our example, we'll need dp[3][6]. Here dp[i][j] will denote the number of ways we can get j if we had coins from coins[0] up to coins[i]. For example dp[1][2] will store if we had coins[0] and coins[1], in how many ways we could make 2. Let's begin:

For dp[0][0], we are asking ourselves if we had only 1 denomination of coin, that is coins[0] = 1, in how many ways can we get 0? The answer is 1 way, which is if we don't take any coin at all. Moving on, dp[0][1] will represent if we had only coins[0], in how many ways can we get 1? The answer is again 1. In the same way, dp[0][2], dp[0][3], dp[0][4], dp[0][5] will be 1. Our array will look like:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

For dp[1][0], we are asking ourselves if we had coins of 2 denominations, that is if we had coins[0] = 1 and coins[1] = 2, in how many ways we could make 0? The answer is 1, which is by taking no coins at all. For dp[1][1], since coins[1] = 2 is greater than our current total, 2 will not contribute to getting the total. So we'll exclude 2 and count number of ways we can get the total using coins[0]. But this value is already stored in dp[0][1]! So we'll take the value from the top. Our first formula:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

For dp[1][2], in how many ways can we get 2, if we had coins of denomination 1 and 2? We can make 2 using coins of denomination of 1, which is represented by dp[0][2], again we can take 1 denomination of 2 which is stored in dp[1][2-coins[i]], where i = 1. Why? It'll be apparent if we look at the next example. For dp[1][3], in how many ways can we get 3, if we had coins of denomination 1 and 2? We can make 3 using coins of denomination 1 in 1 way, which is stored in dp[0][3]. Now if we take 1 denomination of 2, we'll need 3 - 2 = 1 to get the total. The number of ways to get 1 using the coins of denomination 1 and 2 is stored in dp[1][1], which can be written as, dp[i][j-coins[i]], where i = 1. This is why we wrote the previous value in this way. Our second and final formula will be:

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

This is the two required formulae to fill up the whole dp array. After filling up the array will look like:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp[2][5] will contain our required answer. The algorithm:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

The time complexity of this algorithm is O(n * total), where n is the number of denominations of coins we have.