In this post, we will look at the coin change problem dynamic programming approach.

The specialty of this approach is that it takes care of all types of input denominations. This is unlike the coin change problem using greedy algorithm where certain cases resulted in a non-optimal solution.

However, before we look at the actual solution of the coin change problem, let us first understand what is dynamic programming.

1 – What is Dynamic Programming

Dynamic Programming is a programming technique that combines the accuracy of complete search along with the efficiency of greedy algorithms.

The main caveat behind dynamic programming is that it can be applied to a certain problem if that problem can be divided into sub-problems. Also, each of the sub-problems should be solvable independently.

The idea behind sub-problems is that the solution to these sub-problems can be used to solve a bigger problem. Hence, dynamic programming algorithms are highly optimized.

In greedy algorithms, the goal is usually local optimization. However, the dynamic programming approach tries to have an overall optimization of the problem.

2 – Understanding the Coin Change Problem

Let’s understand what the coin change problem really is all about.

According to the coin change problem, we are given a set of coins of various denominations. Consider the below array as the set of coins where each element is basically a denomination.

{1, 2, 5, 10, 20, 50, 100, 500}

Our task is to use these coins to accumulate a sum of money using the minimum (or optimal) number of coins. Also, we can assume that a particular denomination has an infinite number of coins. In other words, we can use a particular denomination as many times as we want.

For example, if we have to achieve a sum of 93 using the above denominations, we need the below 5 coins.

50 20 20 2 1

Let’s consider another set of denominations as below:

{1, 3, 4, 5}

With these denominations, if we have to achieve a sum of 7, we need only 2 coins as below:

3 4

However, if you recall the greedy algorithm approach, we end up with 3 coins (5, 1, 1) for the above denominations. This is because the greedy algorithm always gives priority to local optimization.

3 – Dynamic Programming Solution

The above problem lends itself well to a dynamic programming approach.

The dynamic programming solution finds all possibilities of forming a particular sum. Basically, this is quite similar to a brute-force approach.

Then, you might wonder how and why dynamic programming solution is efficient.

This is because the dynamic programming approach uses memoization. Due to this, it calculates the solution to a sub-problem only once. In other words, we can derive a particular sum by dividing the overall problem into sub-problems.

3.1 – Understanding the Approach

Let’s work with the second example from previous section where the greedy approach did not provide an optimal solution.

coin change problem dynamic programming

In the above illustration, we create an initial array of size sum + 1. Also, we assign each element with the value sum + 1. Since we are trying to reach a sum of 7, we create an array of size 8 and assign 8 to each element’s value. This array will basically store the answer to each value till 7. So, for example, the index 0 will store the minimum number of coins required to achieve a value of 0. Next, index 1 stores the minimum number of coins to achieve a value of 1.

Lastly, index 7 will store the minimum number of coins to achieve value of 7. And that will basically be our answer. However, we will also keep track of the solution of every value from 0 to 7.

To fill the array, we traverse through all the denominations one-by-one and find the minimum coins needed using that particular denomination. As an example, first we take the coin of value 1 and decide how many coins needed to achieve a value of 0. The answer, of course is 0. Next, we look at coin having value of 3. The answer is still 0 and so on.

Once we check all denominations, we move to the next index. Using coin having value 1, we need 1 coin. Using other coins, it is not possible to make a value of 1. Hence, the minimum stays at 1. The main change, however, happens at value 3. Using coins of value 1, we need 3 coins. However, if we use a single coin of value 3, we just need 1 coin which is the optimal solution.

3.2 – Completing the Approach

Following this approach, we keep filling the above array as below:

coin change problem dynamic programming approach

As you can see, we finally find our solution at index 7 of our array. Basically, 2 coins. And that is the most optimal solution.

Considering the above example, when we reach denomination 4 and index 7 in our search, we check that excluding the value of 4, we need 3 to reach 7. And using our stored results, we can easily see that the optimal solution to achieve 3 is 1 coin. Hence, the optimal solution to achieve 7 will be 2 coins (1 more than the coins required to achieve 3). See below highlighted cells for more clarity.

coin change problem

With this understanding of the solution, let’s now implement the same using C++.

3.3 – Implementation of Coin Change Problem in C++

Below is an implementation of the coin change problem using dynamic programming.

#include <bits/stdc++.h>

std::vector<int> denominations = {1, 3, 4, 5};

int findMinCoins(int value)
{
    //Initializing the result array
    std::vector<int> dp(value+1, value+1);

    //Setting the first element to 0
    dp[0] = 0;

    for(int i = 1; i < dp.size(); i++)
    {
        for(int j = 0; j < denominations.size(); j++)
        {
            if(denominations[j] <= i)
            {
                dp[i] = std::min(dp[i], dp[i-denominations[j]] + 1);
            }
            
        }
    }

    return dp[value] == (value + 1) ? - 1 : dp[value];
}

int main()
{
    int minimum_coins = findMinCoins(7);

    std::cout << minimum_coins << std::endl;

    return 0;
}

Basically, here we follow the same approach we discussed. The final results will be present in the vector named dp. We return that at the end.

The time complexity of this solution is O(A * n). Here, A is the amount for which we want to calculate the coins. Also, n is the number of denominations.


With this, we have successfully understood the solution of coin change problem using dynamic programming approach. Also, we implemented a solution using C++.


Saurabh Dashora

Saurabh is a Software Architect with over 12 years of experience. He has worked on large-scale distributed systems across various domains and organizations. He is also a passionate Technical Writer and loves sharing knowledge in the community.

8 Comments

Kornia · July 25, 2021 at 11:54 am

I have searched through a lot of websites and you tube tutorials. This is the best explained post ! However, the program could be explained with one example and dry run so that the program part gets clear. Again this code is easily understandable to people who know C or C++. Thanks a lot for the solution. One question is why is it (value+1) instead of value? any special significance? Is it because we took array to be value+1?

    Saurabh Dashora · July 25, 2021 at 12:13 pm

    Hello,
    Thanks for the great feedback and I agree with your point about the dry run. Will try to incorporate it.

    As to your second question about value+1, your guess is correct.

Ariel Marcelo Pardo · August 12, 2021 at 6:16 pm

hello, i don’t understand why in the column of index 2 all the numbers are 2?

    Saurabh Dashora · August 13, 2021 at 12:37 pm

    Hi, that is because to make an amount of 2, we always need 2 coins (1 + 1). There is no way to make 2 with any other number of coins.

Adam · March 29, 2022 at 3:23 am

Hi, thanks for the clear explanation.

I think there’s a mistake in your image in section 3.2 though: it shows the final minimum count for a total of 5 to be 2 coins, but it should be a minimum count of 1, since we have 5 in our set of available denominations.

    Saurabh Dashora · March 29, 2022 at 4:03 am

    Hi Adam,

    Glad that you liked the post and thanks for the feedback!

    Actually, we are looking for a total of 7 and not 5. Hence, 2 coins.

      Dafe · August 1, 2022 at 8:08 am

      Actually, I have the same doubt… if the array were from 0 to 5, the minimum number of coins to get to 5 is not 2, it’s 1 with the denominations {1,3,4,5}

        Saurabh Dashora · August 1, 2022 at 8:19 am

        Hi Dafe, you are correct but we are actually looking for a sum of 7 and not 5 in the post example.

Leave a Reply

Your email address will not be published. Required fields are marked *