Minimum Coin Change Problem

In this tutorial we shall learn how to solve coin change problem with help of an example and solve it by using Dynamic Programming.

Problem Statement:

You are given a certain coin denomination and a total amount. You need to find min number of coins required to add up to that total amount. You can assume that you have unlimited supply of coins.

Coin Denomination: 1, 2, 5, 7

Total = 7.

The solution will be “5 + 2 = 7” 2 coins.

There can be also “2 + 2 + 2 + 1 = 7” 4 coins. But we need to calculate the min coins required.

We shall solve this by using Dynamic programming approach.

As usual, for DP we should be using a DP table. Let’s see how to solve this problem.

In our example coin denominations are 1, 5, 6 and total = 7.

We shall write our DP array as:

From the above image, we have written down the amount from 0 to 7. It is important to include 0 also.  We have also written the coin combination, so that we get to know the least number of coins required that match the denomination.

So we you have only 1 coin/rupee the number of coins required will be equal to the amount. Hence we can fil the array as below:

Now we shave coin options [1, 5] and now we shall check if we can reduce the number of coins required. Till 4 rupees, the number of coins required will be same as the amount.

When you reach 5, as you have a 5 rupees’ coin, the number of coins required will be 1.

Similarly, when you reach 6, the min coin will be 2. i.e one rupee coin and one 5 rupee coin.

Similarly, when you reach 7, the min coin required will be 3. 2 one rupee coin and one 5 rupee coin.

Now that we have filled the amount by using logic, how can we formulate this logic?

When we reach 5 rupees, the number of coins required is 1. If you check carefully, we took the minimum of the value above or value at 5 steps back + 1.

i.e min(top_value, value_at_5_setps_back+1)

i.e the value at the top at rupee 5 is 5.

The value when you take 5 steps back is “0”.

So min(5, 0 + 1) = 1.

Note that we take the number of steps back, according to the coin value. As of now we are calculating (1, 5). Hence we take 5 steps back.

Next when we calculate for (1, 5, 6) we take 6 steps back.

Similarly, we can do for 6 rupees with 2 coins available

Similarly, for 7 rupees with 2 coin available

Now we have completed calculating when we have 2 coins.

Now we shall calculate when we have 3 coin i.e [1, 5, 6]

Till 5 rupees, we can copy the value from above cell.

When we reach at 6 rupees, we can calculate using the previous formula, now we shall move back 6 steps.

Similarly, we do it at 7 rupees with 3 coins available. Hence our result.

Implementation using Dynamic Programming

#include <iostream>
#include <vector>

using namespace std;


int get_minimum_coin_required(vector<int>& coins, int amount) 
{
    int Max = amount + 1;
    vector<int> dp(amount + 1, Max);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) 
    {
        for (int j = 0; j < coins.size(); j++) 
        {
            if (coins[j] <= i) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}


int main (void) 
{
    vector <int> coins;
    coins.push_back (1);
    coins.push_back (3);
    coins.push_back (6);
    int amount_value = 6;

    int min_coin = get_minimum_coin_required (coins, amount_value);

    cout << min_coin << " is the minimum coin required for amount_value = " << amount_value << "." << endl;
    return 0;
}

Output:

1 is the minimum coin required for amount_value = 6.