Dynamic Programming — Coin Change Problem
A Basic Look into Dynamic Programming — Coin Change Problem
Like many of you out there, I struggle with these higher level questions involving recursion and dynamic programming. My brain finds it difficult to visualize these concepts. Deciphering someone else’s solution often becomes gibberish as you try and follow along with these nested loops and dynamic arrays. I need to have some sort of way to see these problems in a different light to grasp them. Let’s take a look at the ‘Coin Change Problem’.
Given a list of coins (ex. 1 cent, 2 cents, 10 cents) and assuming you have infinite amounts of all coins, how many ways can you make a target amount out of those given coin values?
So for example if our target amount was 12 cents, we want to figure out how many ways we can make 12 cents out of the coins with values 1 cent, 2 cents, and 10 cents.
- 1+1+1+1+1+1+1+1+1+1+1+1 = 12
- 1+1+1+1+1+1+1+1+1+1+2 = 12
- 1+1+1+1+1+1+1+1+2+2 = 12
- 1+1+1+1+1+1+2+2+2 = 12
- 1+1+1+1+2+2+2+2 = 12
- 1+1+2+2+2+2+2 = 12
- 2+2+2+2+2+2 = 12
- 1+1+10 = 12
- 2+10 = 12
We see that there are nine different ways to make the amount 12 cents out of those particular coins. Now…how do we take what we see here and make any sense of it.
So for our problem we have:
N = 12
Index of Coins: [0,1, 2]
Coins:[1,2,10]
We need to come up with a method that can use those coin values and tell us how many ways we can make the amount 12 cents. We will want to split this problem up into smaller subproblems, but save the solutions to those problems so we do not need to calculate anything twice. If a coin is larger than our target amount then we do not need to worry about it and it will not be checked, because we are only going to check up to our target amount.
Let’s define an array that will hold the solutions to our subproblems. We will call this our ways array and each index represents how many ways a given set of coins can make a certain value up to Nth. In our situation we are looking up to 12.
waysArray = [0,0,0,0,0,0,0,0,0,0,0,0,0]
The size of this array will be N + 1, or up to the Nth value (in our case 12 + 1)
The reason for having an array up to the Nth value is so we can determine the number of ways the coins make up the amount at the index of waysArray. If we determine that a coin is larger than the value of the index of our waysArray then we can not use that coin to determine permutations, because the coin is larger than that value.
N = 7
Index of coins = [0,1,2]
coins = [1,2,10]
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [0, 0, 0 ,0, 0, 0, 0, 0, 0, 0 , 0 , 0, 0]
Before we begin we need to give our waysArray a predefined value.
We will set waysArray[ 0 ] = 1. This is because this represents how many ways we can make 0 out of 0.
We will iterate through all the coins and compare the coin to the waysArray index to determine how many times a coin can be used to make the amount at the index of the waysArray.
Let’s start with our 1 cent coin.
N = 7
Index of coins = [0,1,2]
coins = [1,2,10]
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 0, 0 ,0, 0, 0, 0, 0, 0, 0 , 0 , 0, 0]
First compare the coins value to the value of the waysArray index and if it is smaller than or equal. Then, see how many times this set of coins can make that amount. Right now we are just looking at the 1 cent coin, so we begin:
How many ways can we make 1 cent out of 1 cent coins? We can make it one way.
How many ways can we make 2 cents out of 1 cent coins? We can make it one way.
How many ways can we make 3 cents out of 1 cent coins? We can make it one way.
…etc…
You can see the pattern here for the first coin. It makes sense that for any index value there will only be one way to make that amount given 1 cent coins.
Our new value(which is our current number of ways to make this amount with these coins) will be calculated using:
waysArray[ j ] = waysArray[ j — coins[ i ]] + waysArray[ j ]
The first iteration:
waysArray[ 1 ] = waysArray[ 1 — coins[ 0 ]] + waysArray[ 1 ]
waysArray[ 1 ] = waysArray[ 1–1 ] + waysArray[ 1 ]
waysArray[ 1 ] = 1 + 0
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 0 ,0, 0, 0, 0, 0, 0, 0 , 0 , 0, 0]
The second iteration:
waysArray[ 2 ] = waysArray[ 2 — coins[ 0 ]] + waysArray[ 2 ]
waysArray[ 2 ] = waysArray[ 2–1 ] + waysArray[ 2 ]
waysArray[ 1 ] = 1 + 0
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 1 ,0, 0, 0, 0, 0, 0, 0 , 0 , 0, 0]
Once we iterate through each index our waysArray will be:
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 1 ,1, 1, 1, 1, 1, 1, 1 , 1 , 1, 1]
If we look back up at our possible solutions, we see that our 1st solution, 1+1+1+1+1+1+1+1+1+1+1+1 = 12, looks a lot like our waysArray values…
Now we will iterate through our waysArray with the 2 cent coin making the same comparison again. If the value of the coin is smaller than or equal to the value of the index of the waysArray then waysArray[ j ] = waysArray[ j — coins[ i ]] + waysArray[ j ].
For the indices 0–1 we won’t even bother to look at these because we know it is impossible to make the values 0 cents, 1 cent with 2 cents.
When we arrive at index 2 we see that our coin value is less than or equal to 2, so we do:
waysArray[ 2 ] = waysArray[ 2 — coins[1]] + waysArray[ 2 ]
waysArray[ 2 ] = waysArray[ 2–2 ] + waysArray[ 2 ]
waysArray[ 2 ] = 1 + 1
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2 ,1, 1, 1, 1, 1, 1, 1 , 1 , 1, 1]
What is going on here?
We want to determine how many times the second coin (2 cents) goes into all of the values leading up to the Nth (12th) coin. We are using all of the coins to check our previous result and instead of recalculating any values just add it to our new value.
We just calculated that our index at waysArray[ 2 ] = 2
We know that the value 2–2 is equal to 0, this is our j — coins[ i ] value. This is essentially the difference that must be made up in order to make the value 2. We see that waysArray[ 0 ] = 1. This is saying that so far we have calculated 1 way to make 0. So, if there is one way to obtain the value of zero, then that number of ways plus the current number of ways is the new updated total ways to get the amount at index 2. Another way to think about it is we are adding waysArray[ 2 ] (which is equal to 1 and represents how many ways we have currently to make the value of 2). That current value is only the value using the ‘one’ coin, now we must add the ‘two’ coin. The difference of the index value, the coin value, gives us the amount to add. Again 2–2 = 0 and we know that is one way to make zero with zero, so we add this to our current value to get our updated value.
waysArray[ 3 ] = waysArray[ 3 — coins[1]] + waysArray[ 3 ]
waysArray[ 3 ] = waysArray[ 3–2 ] + waysArray[ 3 ]
waysArray[ 3 ] = 1 + 1
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2, 2, 1, 1, 1, 1, 1, 1 , 1 , 1, 1]
Same thing as before, we have j — coins[ i ]
3–2 = 1
Again 1 is the difference that must be made up in order to make the value of 3.
waysArray[ 1 ] = 1
This is saying so far we have calculated 1 way to make the value of 1 with the coins we have checked so far (1 cent, 2 cents).
We add this to the current number of ways to get our updated value of the total ways to get the value at index 3.
waysArray[ 4 ] = waysArray[ 4 — coins[1]] + waysArray[ 4 ]
waysArray[ 4 ] = waysArray[ 4–2 ] + waysArray[ 4 ]
waysArray[ 4 ] = 2 + 1
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2, 2, 3, 1, 1, 1, 1, 1 , 1 , 1, 1]
4 -2 = 2
2 is the difference that must be made up in order to make the value of 4.
waysArray[ 2 ] = 2
So far we have calculated 2 ways to make the value of 2 with the coins (1 cent, 2 cents).
Our current waysArray[ 4 ] = 1, which means we have calculated 1 way to make 4 so far. We know that this number plus the number of ways to make the difference will equal our total number of ways to make our value. We have calculated 2 ways to make 2 which is our difference and add that to our current value of 1 which gives us a new total of 3 different ways to make 4 using (1 cent, 2 cents).
waysArray[ 6 ] = waysArray[ 6 — coins[1]] + waysArray[ 6 ]
waysArray[ 6 ] = waysArray[ 6–2 ] + waysArray[ 6 ]
waysArray[ 6 ] = 3 + 1
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2, 2, 3, 3, 4, 1, 1, 1 , 1 , 1, 1]
When we get done iterating through N with the 2 cent coin we have:
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5 , 6 , 6, 7]
Remember our combinations… lets take a look at what we have so far…
- 1+1+1+1+1+1+1+1+1+1+1+1 = 12
- 1+1+1+1+1+1+1+1+1+1+2 = 12
- 1+1+1+1+1+1+1+1+2+2 = 12
- 1+1+1+1+1+1+2+2+2 = 12
- 1+1+1+1+2+2+2+2 = 12
- 1+1+2+2+2+2+2 = 12
- 2+2+2+2+2+2 = 12
7 combinations… and what is our value at waysArray[ 12 ]? It is 7.
Let’s move onto the last coin 10:
We know that since the value of our coin is 10, then we can skip all the indices with a value lower than 10, because it is impossible to make 0 cents, 1 cent, 2 cents, 3 cents, 4 cents, 5 cents, 6 cents, 7 cents, 8 cents, or 9 cents with 10 cents.
waysArray[ 10 ] = waysArray[ 10 — coins[2]] + waysArray[ 10 ]
waysArray[ 10 ] = waysArray[ 10–10 ] + waysArray[ 10 ]
waysArray[ 10 ] = 1 + 6
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5 , 7 , 6, 7]
waysArray[10] was equal to 6, meaning so far we have found 6 different ways to make the value of 10 with the coins (1 cent, 2 cents). The difference we are trying to find is 10–10 = 0. We know that there is one way to make 0 with 0 so we add waysArray[0] to our current ways to get our updated ways.
waysArray[ 11 ] = waysArray[ 11 — coins[2]] + waysArray[ 11 ]
waysArray[ 11 ] = waysArray[ 11–10 ] + waysArray[ 11 ]
waysArray[ 10 ] = 1 + 6
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5 , 7 , 7, 7]
waysArray[ 11 ] was equal to 6, meaning so far we have found 6 different ways to make the value of 11 with the coins(1 cent, 2 cents). The difference we are trying to find is 11–10 = 1. We know that there is 1 way to make 1 so we add waysArray[1] to our current ways to get our updated ways.
waysArray[ 12 ] = waysArray[ 12 — coins[2]] + waysArray[ 12 ]
waysArray[ 12 ] = waysArray[ 12–10 ] + waysArray[ 12 ]
waysArray[ 12 ] = 2 + 7
Index of waysArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12]
waysArray = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5 , 7 , 7, 9]
waysArray[ 12 ] was equal to 7, meaning so far we have found 7 different ways to make the value of 12 with the coins(1 cent, 2 cents). The difference we are trying to find is 12–10 = 2. We know that so far we have calculated 2 ways to make the value of 2 out of the coins (1 cent, 2 cents). These 2 ways are what we need to add to our current number of ways to make the amount 12 in order to get our updated number of ways using our new coin (10 cents)
Looking back we had 9 combinations total that we could make. We can see our value at waysArray[ 12 ] = 9. This represents the total number of ways we can use the change (1 cent, 2 cents, 10 cents) in order to make the value of 12 cents.
This was a lot…
Now let’s see the code.
