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. 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] = 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.