ronith

10/1/2018 - 1:33 PM

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Optimal Substructure To count the total number of solutions, we can divide all set solutions into two sets.

- Solutions that do not contain mth coin (or Sm).
- Solutions that contain at least one Sm. Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.

```
//https://www.hackerrank.com/challenges/coin-change/problem
// https://www.geeksforgeeks.org/coin-change-dp-7/
#include <iostream>
#include <vector>
using namespace std;
long getWays (long n, vector <long> c) {
/*Look in the description to know the basic algo of the problem.*/
long m= c.size();
long dp[n+1][m]; //rows define the number that should be derived using the coins.
/*Each column denotes a specific type of coin.*/
for (long i=0; i<m; i++)
dp[0][i]=1;
/*row zero means we can get the number by using the coins we have, this increases the no.of ways.*/
for (long i=1; i<n+1; i++) {
for (long j=0; j<m; j++) {
long x= (i- c[j]>=0)?dp[i-c[j]][j]:0;
/*if the number we need to obtain is i, if it is greater than jth coin, then x gives no.of ways we can achieve by using atleast one jth coin*/
long y= (j>0)?dp[i][j-1]:0;
/*y gives no.of ways we can get ith sum by not using jth coin.*/
dp[i][j]= x+y;
}
}
return dp[n][m-1];
}
int main () {
long n, m;
cin>> n>>m;
vector <long> c(m);
for (int i=0;i<m;i++)
cin>>c[i];
cout<< getWays (n, c);
}
```