Related Tags

interview
c++
communitycreator

# Minimum coin change in C++ - a dynamic programming question

Harsh Jain

## Problem introduction

In this article, I will solve a famous problem using the dynamic programming (DP) approach. The name of the problem is minimum coin change and it is very popular in interviews. The problem statement is:

If we want to make change for a given value (N) of cents, and we have an infinite supply of each of C = { $C_{1}$, $C_{2}$, … , $C_{M}$} valued coins, what is the minimum number of coins required to make the change?

Example ->
Input:
coins[] = {25, 10, 5}, N = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents.
Input:
coins[] = {9, 6, 5, 1}, N = 13
Output: Minimum 3 coins required
We can use one coin of 6 + 6 + 1 cents coins.


Before moving on to ​the solution, I would like you to try this on your own first.

## Solution

### 1. Recursive Approach

Start the solution with $sum = N$ cents and, in each iteration, find the minimum coins required by dividing the problem into sub-problems where we take a coin from {$C_{1}$, $C_{2}$, …, $C_{M}$} and decrease the sum, $N$, by $C[i]$ (depending on the coin we took). Whenever $N$ becomes 0, this means we have a possible solution. To find the optimal answer, we return the minimum of all answers for which $N$ became 0.

### Base case

If N == 0, then 0 coins are required.

### Recursive case

If N > 0 then,

minCoins(N , coins[0..m-1]) = min {1 + minCoins(N-coin[i], coins[0....m-1])}


where i varies from 0 to m-1 and coin[i] <= N.

#include<bits/stdc++.h>
using namespace std;

// Recursive Function
int minCoins(int coins[], int m, int N)
{
// base case
if (N == 0)
return 0;

// Initialize result
int res = INT_MAX;

// Try every coin that has smaller value than m
for (int i=0; i<m; i++)
{
if (coins[i] <= N)
{
int sub_res = 1 + minCoins(coins, m, N-coins[i]);
// see if result can minimized
if (sub_res < res)
res = sub_res;
}
}
return res;
}

int main() {
int coins[] = {1,2,3,4,5};
int sum = 11;
int total_coins = 5;
cout << minCoins(coins,total_coins,sum);
}
Recursive solution to the problem

It is easy to see that recursive solutions can require high computations.

You can check this by changing the sum variable’s value to a high value to see an execution time error, which means that our solution is not optimized. This is where most candidates fail in their interviews.

Let’s try dynamic programming now!!

### 2. Dynamic programming approach

Since the same subproblems are computed again and again, this problem has the overlapping subproblems property.

Like other typical dynamic programming problems, re-computations of the same subproblems can be avoided by constructing a temporary array dp[] and memoizing the computed values in that array.

#include <bits/stdc++.h>
using namespace std;

int coins[] = {1,2,3,4,5};
int dp [1000] = {0};
int minCoins(int N, int M)
{
//Initializing all values to INT_MAX i.e. minimum coins to make any
//amount of sum is INT_MAX
for(int i = 0;i<=N;i++)
dp[i] = INT_MAX;

//Base case
//Minimum coins to make sum = 0 cents is 0
dp[0] = 0;

//Iterating in the outer loop for possible values of sum between 1 to N
//Since our final solution for sum = N might depend upon any of these values
for(int i = 1;i<=N;i++)
{
//Inner loop denotes the index of coin array.
//For each value of sum, to obtain the optimal solution.
for(int j = 0;j<M;j++)
{
//i —> sum
//j —> next coin index
//If we can include this coin in our solution
if(coins[j] <= i)
{
//Solution might include the newly included coin
dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
}
}
}
return dp[N];
}

int main() {
int sum = 50;
int total_coins = 5;
cout << minCoins(sum, total_coins);
}
Dynamic programming solution to the problem

So, that’s the dynamic programming approach. We used memoization, saved the solution of the subproblems, and then returned the optimal solution.

The complexity is $O(M*N)$ in this solution, where $M$ is the number of coins and $N$ is the change required. You can see that, because of memoization, we get the output pretty fast, even with a higher value of sum.

As an exercise, try to implement one more solution that uses recursion and dynamic programming. It is usually called the top-down dynamic programming approach. The approach we discussed here is bottom-up.

RELATED TAGS

interview
c++
communitycreator

CONTRIBUTOR

Harsh Jain
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time