Home Practice Programming DP - Coin Change: Find number of ways of representing n cents

DP – Coin Change: Find number of ways of representing n cents

Given an infinite supply of 25 cents, 10 cents, 5 cents, and 1 cent. Find the number of ways of representing n cents. (The order doesn’t matter). This is a coin change problem and will require the implementation of Dynamic Programming.

Ex: n = 10 => {1,1,1,1,1,1,1,1,1,1}
              {1,1,1,1,1,5}
              {5,5}
              {10}

Algorithm:

We are given a set of 4 Coins of type 1 cents, 5 cents, 10 cents, 25 cents. To find the number of ways of making n cents using these 4 cents, we will consider 2 conditions:

  1. Try to make n cents by including the ith cent from the set of 4 coins. number_of_ways(n-coin_arr[m], coin_arr m);  here m in the number of coins in given set(here m=4).
  2. Try to make n cents by not including the ith cent from the given set of the 4 coins.                                 number_of_ways(n, coin_arr, m-1);

This problem involves the repetition of subproblems, so we will use Dynamic Programming.

Coin Change - The number of ways of representing 6 cents using 1cents and 2 cents. (Here for simplicity we have considered a set of 2 coins only)
The number of ways of representing 6 cents using 1cents and 2 cents. (Here for simplicity we have considered a set of 2 coins only)

Implementation of the above Algorithm

1. Iterative Approach

#include <bits/stdc++.h>
using namespace std;
 
int number_of_ways(int cents, vector<int>coin_arr, int n){
    vector<vector<int> >dp(n+1, vector<int>(cents+1,0));
 
    for(int j=0; j<n; j++)
        dp[j][0] = 1;
     
    for(int i=1; i<=cents; i++){
        for(int j=0; j<n; j++){
             
            if(i-coin_arr[j]>=0) dp[j][i] += dp[j][i-coin_arr[j]];
            if(j>0) dp[j][i] += dp[j-1][i];
 
        }
    }
    return dp[n-1][cents];
}
 
int main()
{
    int cents;
    vector<int> coin_arr{1,5,10,25};
    cin>>cents;
 
    cout<<number_of_ways(cents, coin_arr, coin_arr.size())<<endl;
 
    return 0;
}

2. Recursive Approach

#include <bits/stdc++.h>
using namespace std;
 
int number_of_ways(int cents, vector<int>coin_arr, int n, vector<vector<int> > &dp){
 
    if(cents<0 || n<0)
        return 0;
 
    if(cents == 0)
        return 1;
 
    if(dp[cents][n]==-1)
        dp[cents][n] =  number_of_ways(cents-coin_arr[n], coin_arr, n, dp) +number_of_ways(cents, coin_arr, n-1, dp);
    return dp[cents][n];
}
 
int main()
{
    int cents;
    vector<int> coin_arr{1,5,10,25};
    cin>>cents;
    //creating a 2D array for storing subproblems 
    //of size= dp[cents+1][coin_arr.size()+1]
    vector<vector<int> > dp(cents+1, vector<int>(coin_arr.size()+1,-1));
 
    cout<<number_of_ways(cents, coin_arr, coin_arr.size()-1, dp)<<endl;
 
    return 0;
}

Output

Coins       Output
n = 5        2
n = 26       13
n = 1000     142511

Time Complexity

Since we have used Dynamic Programming here, hence the time complexity of the above program for coin change problem is O(NM), N the total cents to make and M is the number of the coin in a given set.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promsie, we won't spam
Even we hate spam as much as you hate them

Books recommendation for interview preparation