Coin change problem in C++

In our problem set, we are given S supply of coins {s1,s2,s3….sn}. We have to make a change for N rupees. We have to count the number of ways in which we can make the change. This is the basic coin change problem in c++ which we will solve using dynamic programming.

Dynamic programming is basically an optimization over recursion. Whenever we see many recursive calls in a program, we build a table to store these values to avoid computing them again. The table is updated in every recursive call and can be filled using any logic. Also, wherever we see overlapping subproblems we can use dynamic programming. This reduces time complexity from exponential to polynomial.

Algorithm

For example-

N=4 and S={1,2,3} then, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So the output should be 4 ways.

N=11 and S={4,5,6,7} then, there are two solutions: {4,7} and {6,5}. So the output should be 2 ways.

Coin change problem in C++

The above tree shows the repeated calling of subproblems so we can use dynamic programming here. The function C{(1),3} is called two times. If we draw the complete tree, there will be many subproblems repeated. Thus, we can use the table to store the values in a bottom-up manner to avoid repeated calculations.

Coin change problem in C++

Code:

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

int countchange( int arr[], int row, int col ) 
{ 
  int k, j, x, y; 

  int dp[col + 1][row]; 
  
  for (j = 0; j < row; j++) 
    dp[0][j] = 1; 

  
  for (k = 1; k < col + 1; k++) 
  { 
    for (j = 0; j < row; j++) 
    { 
      
      if(k-arr[j] >= 0) 
            {
                 x=dp[k - arr[j]][j]; 
            } 
            else{
                x=0;
                } 
           
            if(j >= 1) 
            { y=dp[k][j - 1];
             } 
             else
             {
                 y=0;
                }
             // total count 
             dp[k][j] = x + y;
         } 
  } 
  return dp[col][row - 1]; 
} 


int main() 
{ 
  int arr[] = {1, 2, 3,4}; 
  int m = 4; 
  int n = 6; 
  cout << countchange(arr, m, n); 
  return 0; 
} 


 

Output:

9

The dp table can be seen below for the above input.

dp table c++

table[6][3] will be the answer which shows that by including coins up to 3 and n=6, there are 9 ways. The block table[4][1] shows that n=4 and we can only use coins 0 and 1 and the ways for that are 3.

Time complexity: o(mn)

See, how the time complexity is reduced and the problem is solved easily.

Also, refer to:

Count the number of occurences in C++

 

Thank you! Please comment on suggestions…

Leave a Reply

Your email address will not be published. Required fields are marked *