Coin Change Problem Number of Ways to Get Total By Dynamic Programming

Different types of coins available to you in infinite quantities to find out the total number of ways you can make the change of the given amount using the given coins.

 

Example: 

There are 4 coins 2, 5, 3, 6 and finds the number of ways to make the change for n=10. You have infinite numbers of coins. There are five ways to change 10 using the following coins. There are 5 ways to change 10 using these 4 coins.

1. {2, 2, 2, 2, 2}
2. {2, 2, 3, 3}
3. {2, 2, 6}
4. {2, 3, 5}
5. {5, 5}

 

Questions: 

You are given 4 coins {2, 3, 5, 10} your task is to find the number of ways to make the changes for 15 units. You have infinite numbers of coins available. 

Answer:

The first row is weight from 0 to 15 because here we are finding the number of ways we can change 15 and the first column is the available coins. We can skip the second row.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	1	0	0+1 =1	0+0 =0	0+1 =1	0+0 =0	0+1 =1	0+0 =0	0+1 =1	0+0 =0	0+1 =1	0+0 =0	0+1 =1	0+0 =0	0+1 =1	0+0 =0
3	1	0	1	0+1 =1	1+0 =1	0+1 =1	1+1 =2	0+1 =1	1+1 =2	0+2 =2	1+1 =2	0+2 =2	1+2 =3	0+2 =2	1+2 =3	0+3 =3
5	1	0	1	1	1	1+1 =2	2+0 =2	1+1 =2	2+1 =3	2+1 =3	2+2 =4	2+2 =4	3+2 =5	2+3 =5	3+3 =6	3+4 =7
10	1	0	1	1	1	2	2	2	3	3	4+1 =5	4+0 =4	5+1 =6	5+1 =6	6+1 =7	7+2 =9

The last cell is the result. Here the result is 9.

 

If the coin's value is less than the column's weight then just copy the value from upper cell.

• matrix[i][j] = matrix[i - 1][j]

If coin value is greater than or equal to weight then do the following task.

• matrix[i][j] = matrix[i - 1][j] + matrix[i][j - coins[i]]

 

Python Implementation:

def coin_change(coins, weight):
    coins.sort()
    coins.insert(0, 0)
    matrix = [[None for _ in range(weight + 1)] for j in range(len(coins))]
    matrix[0][0] = 1
    for j in range(1, weight + 1):
        matrix[0][j] = 0

    for i in range(1, len(matrix)):
        for j in range(weight + 1):
            if coins[i] > j:
                matrix[i][j] = matrix[i - 1][j]
            else:
                matrix[i][j] = matrix[i - 1][j] + matrix[i][j - coins[i]]

    return matrix[-1][-1]


if __name__ == '__main__':
    available_coins = [2, 3, 5, 10]
    total = 15
    print(coin_change(available_coins, total))

Output:

9

 

Time complexity: O(n * w)