## Dry run

Below is the table generated when we try to run the algorithm with the following inputs:

Sum = 10

**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

1 2 3 4 5 6 7 8 |
public class Coins { public static void main(String[] args) { int[] denominations = new int[] { 1, 3, 5, 7 }; int sum = 10; printArray(NumberOfCoins(sum, denominations)); } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public static int[] NumberOfCoins(int sum, int[] denominations) { int[] a = new int[sum + 1]; Arrays.fill(a, Integer.MAX_VALUE-1000); a[0]=0; for (int i = 0; i <= sum; i++) { for (int j = denominations.length - 1; j >= 0; j--) { if (denominations[j] <= i) { a[i] = Math.min(1 + a[i - denominations[j]], a[i]); } } } return a; } public static void printArray(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } } |

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