Trusted answers to developer questions
Trusted Answers to Developer Questions

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 = { C1C_{1}, C2C_{2}, … , CMC_{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=Nsum = N cents and, in each iteration, find the minimum coins required by dividing the problem into sub-problems where we take a coin from {C1C_{1}, C2C_{2}, …, CMC_{M}} and decrease the sum, NN, by C[i]C[i] (depending on the coin we took). Whenever NN becomes 0, this means we have a possible solution. To find the optimal answer, we return the minimum of all answers for which NN 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() {
  // your code goes here
  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(MN)O(M*N) in this solution, where MM is the number of coins and NN 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.

Thanks for reading!!

RELATED TAGS

interview
c++
communitycreator
RELATED COURSES

View all Courses

Keep Exploring