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

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);
}

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);
}

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.

Thanks for reading!!

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments