Part-5 , (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?       



                                                  Dynamic Programming Solutions of
                                                        these kinds of solution

int count( int S[], int m, int n )

{

    // table[i] will be storing the number of solutions for

    // value i. We need n+1 rows as the table is consturcted

    // in bottom up manner using the base case (n = 0)

    int table[n+1];

 

    // Initialize all table values as 0

    memset(table, 0, sizeof(table));

 

    // Base case (If given value is 0)

    table[0] = 1;

 

    // Pick all coins one by one and update the table[] values

    // after the index greater than or equal to the value of the

    // picked coin

    for(int i=0; i<m; i++)

        for(int j=S[i]; j<=n; j++)

            table[j] += table[j-S[i]];

 

    return table[n];

}

 

int main()

{

    int arr[] = {1, 2, 3};

    int m = sizeof(arr)/sizeof(arr[0]);

    int n = 4;

    printf(" %d ", count(arr, m, n));

    return 0;

}

 

 

           Problem : https://practice.geeksforgeeks.org/problems/coin-change/0

 

 

 

#include<bits/stdc++.h>

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int count( int S[], int m, int n )
{
    int dp[n+1];

    memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for(int i=0; i<m; i++){
        for(int j=S[i]; j<=n; j++){
            dp[j] += dp[j-S[i]];
        }
    }

    return dp[n];
}

int main()

{
    int t,s,x,N;
    cin>>t;
    while(t--)
    {
        cin>>s;
        int A[s];
        for(int i=0;i<s;i++)
        {
            cin>>A[i];
        }
        cin>>N;
        cout<<count(A,s,N)<<endl;
    }
    return 0;

}