The Coin Change Problem[hackerRank solution]

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

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.

This problem can be solved by using 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).

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

Code:

#include <bits/stdc++.h>

using namespace std;

long getWays(long amount, vector < long > coins)
{
 long size = coins.size();
 long i,j, noofways[size+1][amount+1];
 
 
 for( j=0;j<amount+1;j++)
 {
 noofways[0][j] = 0;
 }
 for( i=0;i<size+1;i++)
 {
 noofways[i][0] = 1;
 }
 for(i =1 ;i<size+1;i++)
 {
 for( j=1;j<amount+1;j++)
 {
 if(coins[i-1]<=j)
 {
 noofways[i][j] = noofways[i-1][j] + noofways[i][j-coins[i-1]];
 
 }
 else
 noofways[i][j] = noofways[i-1][j];
 }
 }
 //matrix
 /*
 for(i=0;i<size+1;i++)
 {
 for(j=0;j<amount+1;j++)
 {
 cout<<noofways[i][j]<<" ";
 }
 cout<<endl;
 }
 
 cout<<endl;
 cout<<size<<" "<<amount<<endl;
 */
 return noofways[size][amount];
 
 
}

int main() {
 int n;
 int m;
 cin >> n >> m;
 vector<long> c(m);
 for(int c_i = 0; c_i < m; c_i++){
 cin >> c[c_i];
 }
 // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
 long ways = getWays(n, c);
 cout<<ways;
 return 0;
}

Runs all test cases.