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.

1 2 3 4 5 6 7 |
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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#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 |
1 is the minimum coin required for amount_value = 6. |