# Coin Change Problem

## Coin Change Problem

In the coin change problem, we have to count the number of ways of making change given an infinite supply of some coins. Here is a C++ implementation explaining the bottom-up and top-down solutions. ## Coin Change Problem Description

We are given a value N ( rupees ). And we are given infinite value of M coins. What are the total number of ways we can make change using m coins. The order of coins doesn’t matter.

Input:

• First line containing integer denoting total rupees for which we have to make change.
• Second line contains integer m denoting number of coins.
• Third line contains m integers denoting the denomination of each coin.

Output:

• Number of ways to make change.

## Coin Change Problem Solution Explanation

### Solution (Top Down):

To build a top down solution we must follow the following steps –

• Break Down the Problem –Since the order of a coin does not matter, the idea is to pick a coin and keep using it till you can. If at any point we decided to not pick the coin then we never pick this coin again. The recurrence relation is –

F(i,N) = Number of ways to make change of N using first i coins.

F(i,N) = F(i,N-coin[i]) + F(i-1,N) { ie using ith coin or not using ith coin}

• Find the base case – We know if N is zero then we have 1 way which is 0 coins . If N becomes negative then there are zero ways. And the third base case is when we are left with zero coins but a positive value of N.
• Check for optimal substructure and overlapping sub problems – It is easy to see that the problem can be broken down into smaller problems. The optimal substructure and overlapping sub problems properties can be visualized below. ### C++ Code:

#include <bits/stdc++.h>
using namespace std;
int dp;
// cur means current coin index
// changeLeft means amount we want to change
int f(int coin[], int curint changeLeft)
{
// If no change left
if (changeLeft == 0)
return 1;
// If change left is negative
if (changeLeft < 0)
return 0;

// If no coin is left and we have positive value of money left.
if (cur < 0 && changeLeft >= 1)
return 0;

if (dp[cur][changeLeft] != –1)
return dp[cur][changeLeft];

return dp[cur][changeLeft] = f(coincur – 1changeLeft) + f(coincurchangeLeft – coin[cur]);
}
int main()
{
memset(dp, –1, sizeof dp);
int n;
cin >> n;
int m;
cin >> m;
int coin[m];
for (int i = 0i < mi++)
{
cin >> coin[i];
}

cout << “Number of ways “ << f(coinm – 1n<< endl;
return 0;
}

### Output:

`631 2 3Number of ways 7`

## Solution (Bottom Up)

For bottom up solution the idea is similar as above. We create a dp table where,

dp[i] = Number of Ways to make change for i rupees.

Now we just pick one coin at a time and fill the dp table.

### C++ Code:

#include <bits/stdc++.h>
using namespace std;
int f(int coin[], int nint m)
{
int dp[n + 1] = {0};
dp = 1;
for (int i = 0i < mi++)
{
// Pick and use ith coin
for (int j = coin[i] ; j <= nj++)
{
dp[j] += dp[jcoin[i]];
}
}
return dp[n];
}
int main()
{
int n;
cin >> n;
int m;
cin >> m;
int coin[m];
for (int i = 0i < mi++)
{
cin >> coin[i];
}

cout << “Number of ways “ << f(coinnm<< endl;
return 0;
}

### Output:

`631 2 3Number of ways 7`