Dynamic Programming – Minimum Number of Coins

Dry run

Below is the table generated when we try to run the algorithm with the following inputs:
Sum = 10
tablecoin
How did we populate this table
Well, this is very simple and if we dry run the algorithm on the given input, it will automatically populate the table. I will write down the steps for Sum[0] to Sum[4] and that can be extended for the rest.
Initialize the whole array A with infinity or a very large number.

Outer Iteration 1
i = 1
j = 4
Denominations[4] which is 7 is not less than or equal to i i.e. 1. Decrement j to 3 .
Denominations[3] which is 5 is not less than or equal to i i.e. 1. Decrement j to 2 .
Denominations[2] which is 3 is not less than or equal to i i.e. 1. Decrement j to 1 .
Denominations[1] which is 1 is equal to i i.e. 1. Hence we change the value A[1] = Math.min(1 + A[1 – Denominations[1]], A[1]). That makes A[1] = 1.

Outer Iteration 2
i = 2
j = 4
Denominations[4] which is 7 is not less than or equal to i i.e. 2. Decrement j to 3 .
Denominations[3] which is 5 is not less than or equal to i i.e. 2. Decrement j to 2 .
Denominations[2] which is 3 is not less than or equal to i i.e. 2. Decrement j to 1 .
Denominations[1] which is 1 is less than i i.e. 2. Hence we change the value A[2] = Math.min(1 + A[2 – Denominations[1]], A[2]). That makes A[2] = 1 + 1 = 2.

Outer Iteration 3
i = 3
j = 4
Denominations[4] which is 7 is not less than or equal to i i.e. 3. Decrement j to 3 .
Denominations[3] which is 5 is not less than or equal to i i.e. 3. Decrement j to 2 .
Denominations[2] which is 3 is equal to i i.e. 3. Hence we change the value A[3] = Math.min(1 + A[3 – Denominations[2]], A[3]). That makes A[3] = 1. Decrement j to 1.
Denominations[1] which is 1 is equal to i i.e. 3. Hence we change the value A[3] = Math.min(1 + A[3 – Denominations[1]], A[3]). That makes A[3] = 1.

Outer Iteration 4
i = 4
j = 4
Denominations[4] which is 7 is not less than or equal to i i.e. 4. Decrement j to 3 .
Denominations[3] which is 5 is not less than or equal to i i.e. 4. Decrement j to 2 .
Denominations[2] which is 3 is less than i i.e. 4. Hence we change the value A[4] = Math.min(1 + A[4 – Denominations[2]], A[4]). That makes A[4] = 2. Decrement j to 1.
Denominations[1] which is 1 is less than i i.e. 4. Hence we change the value A[4] = Math.min(1 + A[4 – Denominations[1]], A[4]). That makes A[4] = 2.

And so on, we reach to the tenth and eleventh iteration to populate A[10] and A[11].

Source Code

Note: This is a change made after a comment was made by Shivani. For more information please check the comments

Conclusion

So this is how we can implement dynamic programming at a simpler level to calculate the minimum number of coins required to achieve a sum when there is a restriction on the denominations. This is a very famous question and it is asked in multiple interviews.

Hope this helps, happy learning.