Change Making Dynamic Programming Algorithm

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

Video made by April Crockett for Design of Algorithms in April 2020
Video made by Mark Ralph for Design of Algorithms in May 2020
Video made by Daniel Simpson for Design of Algorithms in April 2020
Video made by Alexander Clifford for Design of Algorithms in May 2020

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. 

F0123456
       

Step Two

Then, set F[0] to 0.

F0123456
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.

F0123456
01     

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.

F0123456
012    

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.

F0123456
0121   

i=4

F[4] = minimum{F[4-1],F[4-3],F[4-4]}+1 = 1

F0123456
01211  

i=5

F[5] = minimum{F[5-1],F[5-3],F[5-4]}+1 = 2

F0123456
012112 

i=6

F[6] = minimum{F[6-1],F[6-3],F[6-4]}+1 = 2

F0123456
0121122

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)