ronith
10/1/2018 - 1:33 PM

Coin change

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.

  1. Solutions that do not contain mth coin (or Sm).
  2. 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.

Coin change.cpp
content_copyfile_download
//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);
}