Coin Change Problem using Dynamic Programming

This is a C++ Program that Solves Coin Change Problem using Dynamic Programming technique.

Problem Description

There are infinite number of coins of x different values. These values are given. Using these coins, you have to make change for Rs. N. In how many ways, you can make this change?

Note that there are infinite number of coins of each given value.

Problem Solution

This problem can be solved by using Bottom-up dynamic programming. First we will calculate the no. of ways to change a smaller amount. This can be calculated by finding out no. of ways to change the required amount by once including a coin and once excluding it. Then we will store this value in a matrix. Now, using these values, we will calculate the result for a bigger amount.

The time complexity of this solution is O(N*x).

Expected Input and Output

Case-1:

N=10
x=4
coin[]={2,5,3,6}
 
Expected result=5 
 
Possible combinations are -
2+2+2+2+2
5+5
2+3+5
2+2+3+3
2+2+6

Case-2:

N=4
x=3
coin[]={1,2,3}
 
Expected result=4
 
Possible combinations are -
1+1+1+1
1+1+2
1+3
2+2

Program/Source Code

Here is source code of the C++ Program to Solve Coin Change Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

```
#include<iostream>
```
```
using namespace std;
```
```
 
```

int coinChange(int coin[], int x, int N)

```
{
```
```
    int i,j;
```
```
 
```

    //make a matrix of size (N+1)*x to tabulate the computed values

```
    int dp[N+1][x];
```
```
 
```

    //dp[i][j] represents no.of ways in which change of Rs. i can be made with just j type of coins available

```
 
```
```
    int including,excluding;
```
```
 
```
```
    //initialization
```

    //since, there is only one way in which change of Rs. 0 can be made ie., not including any coin

```
    for(j=0;j<x;j++)
```
```
    {
```
```
        dp[0][j]=1;
```
```
    }
```
```
 
```

    //i represents the amount whose change is required

```
    for(i=1;i<=N;i++)
```
```
    {
```

        //j represents the coin values available

```
        for(j=0;j<x;j++)
```
```
        {
```

            //if the the value of current coin is less than or equal to total amount whose change is required

```
            //include this coin
```
```
            if(i>=coin[j])
```
```
            {
```

                including=dp[i-coin[j]][j];

```
            }
```
```
 
```
```
            else
```
```
                including=0;
```
```
 
```

            //excluding will store the number of ways in which the amount can be changed without including the current coin value

```
            if(j>=1)
```
```
                excluding=dp[i][j-1];
```
```
 
```
```
            else
```
```
                excluding=0;
```
```
 
```

            //dp[i][j] will be the sum of no.of ways by including as well as excluding the current coin

            dp[i][j]=including+excluding;

```
        }
```
```
    }
```
```
 
```
```
    return dp[N][x-1];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i;
```

    int x;  //number of distinct values of coins

    int N;  //amount whose change is required

```
 
```

    cout<<"Enter the amount whose change is required"<<endl;

```
    cin>>N;
```
```
 
```

    cout<<"Enter the number of distinct values of coins"<<endl;

```
    cin>>x;
```
```
 
```
```
    //distinct values of coins
```
```
    int coin[x];
```
```
 
```

    cout<<"Enter the values of coins"<<endl;

```
    for(i=0;i<x;i++)
```
```
        cin>>coin[i];
```
```
 
```

    cout<<"No. of ways in which Rs."<<N<<" can be changed is ";

```
    cout<<coinChange(coin,x,N);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the amount of change required, number of coins available and the value of coins. We pass these values to the function coinChange as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ coin_change.cpp
$ ./a.out
Enter the amount whose change is required
10
Enter the number of distinct values of coins
4
Enter the values of coins
2
5
3
6
No. of ways in which Rs.10 can be changed is 5

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

If you find any mistake above, kindly email to [email protected]

« Prev - Binomial Coefficient using Dynamic Programming

» Next - Fibonacci Series using Dynamic Programming

Related Posts:

Recommended Articles: