The Coin Change Problem — Explained

I hope to provide a step-by-step walkthrough of the Dynamic Programming solution to this problem.

This article is assuming that the reader is already versed in the recursive solution. If there are many questions on that one, I will follow up by editing this post. Or I might just come back to edit it anyway.

Let’s start with looking at the code. I will be using Python and be breaking down what happens in the key parts of the script. This is called a bottom-up approach because we are working our way up the indexes instead of recursion which is done by looking to decrement indexes until termination.

The function takes S (the coins list), m (the length of the coins list) and n (the change we want to make up). In this article , we shall use the simple but sufficiently representative case of S=[ 1,2,3 ] and n = 4.

In the red box below, we are simply constructing a table list of lists, with length n+1. We are first initialising all values in the individual lists to be 0. Then after that we will be initialising the first list in the table to all ‘1’s. Why is this so? Let’s move on to understand why.

The function to find the number of combinations.

First, let’s get comfortable with looking and understanding the figure below completely. With our case of n = 4 and S = [ 1,2,3 ],

The variables we will be working with are as follows: S is the input list, j is the index tracking each S. The number of lists in table are initialised to n + 1, to accommodate the base case of n=0. Why are they filled with ‘1’s? This is so that the program will always return 1 when n=0, similar to the recursive solution to this problem.

Next, let’s look at what happens in the nested for loops.

We will be iterating through each list in table starting from index 1, and within each iteration we will be iterating through S. In this way, we accumulatively compute and would be able to avoid duplicated computations moving forward.

By implementing it in nested for loops and incrementing the indexes, we call it a bottom up approach.

What the nested for loops represent

Now comes the tricky part (at least for me when I was studying it). Let’s focus on the two statements inside the nested for loop. These two statements are executed for every element in each list in table starting from n=1.

Let’s look at the two lines of code:

Similar to the recursive solution, for each iteration of the inner loop, we want to get the solutions which compulsorily includes S[ j ] and store it in x, and also get the solutions which compulsorily excludes S[ j ] and store it in y. In doing so, we would be able to reference earlier solutions to avoid duplicate computations.

Why do it this way of including and excluding the coin S[ j ] for each computation?

The explanation is simple. For each coin, there can be only two possibilities; to include it or exclude it in consideration with that value of n. And we know that if the coin (which is S[ j ]) is larger than n, then x would return 0 since including it into consideration would be impossible.

Now, let’s start with two questions:

1. What is the significance of i — S[ j ] ?

The value of previous i to reference after S[ j ] is taken from i. Including S[ j ] is compulsory.

2. Why reference [ j ] ?

We want to reference the same position in S, which is S[ j ], just at a different n.

3. Why is it used as an index for table array ?

To reference earlier calculations of n arrays.

What the two statements mean:

1.First Statement

By making S[ j ] compulsory, we deduct S[ j ] from i and reference the past computed n, where n = i — S[ j ].

2.Second Statement

Finding out all the solutions which exclude S[ j ] by referencing the previous computed S[ j ] = S[ j ] — 1. Let’s dive deeper.

Let’s Deep Dive into Second Statement:

1.What is the significance of [ i ][ j-1 ]?

Referencing the same n, in the previous element of S.

2.Why make it always return 0 when j<1 ?

When j = 0, we are not considering any S[ j ].

3. In that case, does the list S have to be sorted?

No, since we are accumulatively iterating through m working towards when j=m and only interested in the final case.

4. How about the case of using S[0] and S[2] but NOT s[1]?

We do not need to compute that, since ultimately we want to know how many solutions exist for i==n after iterating through all the coins in the coins array.

Now, let’s start running through the nested for loops with the test values.

Let’s run through the nested for loops.

Illustration of the steps above.

I hope that this post is able to help people who are trying to understand this problem. Pardon me that I did not really spend time on the aesthetics, hope the content would make up for it.

Please also refer to the Dynamic Programming Solution from the Geeksforgeeks website and read through the post:

Dynamic Programming | Set 7 (Coin Change) - GeeksforGeeks_Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm}…_www.geeksforgeeks.org