Give change for amount (n) using the minimum number of coins of denominations (d1 < d2 < … < dm).
There is also a greedy algorithm to solve this problem but this post is on the dynamic programming technique algorithm.
In this problem, we assume that there is an unlimited quantity of coins for each of the m denominations. In other words, we will never run out of change.
Videos
Algorithm Steps on Sample Input
Step One
Create an array of size amount +1. Four our example, the array would be 7 elements since the amount is 6.
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Step Two
Then, set F[0] to 0.
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 |
Step Three: (repetitive part)
Iterate through each index of the table using the formula F[i] = minimum of {F[i-1], F[i-3], F[i-4]} + 1
i = 1
F[1] = minimum{F[1-1]}+1 = 1
Note that we do not worry about coin 3 or 4 when i is equal to one because 1 is smaller than coin 3 or 4.
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 1 |
i=2
F[2] = minimum{F[2-1]} + 1 = 2
Again we didn’t worry about coin 3 or 4 when i is equal to two because 2 is smaller than coin 3 or 4.
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 1 | 2 |
i=3
F[3] = minimum{F[3-1],F[3-3]}+1 = 1
We didn’t worry about coin 4 because when i is equal to 3 is smaller than coin 4.
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 1 | 2 | 1 |
i=4
F[4] = minimum{F[4-1],F[4-3],F[4-4]}+1 = 1
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 1 | 2 | 1 | 1 |
i=5
F[5] = minimum{F[5-1],F[5-3],F[5-4]}+1 = 2
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 1 | 2 | 1 | 1 | 2 |
i=6
F[6] = minimum{F[6-1],F[6-3],F[6-4]}+1 = 2
F | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 1 | 2 | 1 | 1 | 2 | 2 |
Output
The algorithm returns F[6] as the output, which is 2. This is the least amount of coins that we can give as change with the given input is 2.
Which coin produced the minimum value for i=6? It was coin 3.
Pseudocode
ALGORITHM ChangeMaking(D[1..m],n)
//Input: Postitive integer na nd array D[1..m] of increasing positive integers indicating the coin denominations where D[1]=1
//Output: The minimum number of coins that add up to n
F[0] = 0;
for(i=1; i<n; i++){
temp = infinity;
j = 1;
while(j <=m and i>=D[j]){
temp = min(F[i-D[j]],temp);
j=j+1;
}
}
return F[n];
Time & Space Efficiency
Time: ϴ(mn)
Space: ϴ(n)