Dynamic Programming | Set 7 (Coin Change) | GeeksforGeeks

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.
From http://www.algorithmist.com/index.php/Coin_Change

Recursive Formulation

We are trying to count the number of distinct sets.

Since order does not matter, we will impose that our solutions (sets) are all sorted in non-decreasing order (Thus, we are looking at sorted-set solutions: collections).

For a particular N and  (now with the restriction that , our solutions can be constructed in non-decreasing order), the set of solutions for this problem, C(N,m), can be partitioned into two sets:

• There are those sets that do not contain any S_m and
• Those sets that contain at least 1 S_m

This partitioning will essentially break the initial problem into two subproblems:

1. If N < S_m (that is, a solution does not contain S_m), then we can solve the subproblem of N with , or the solutions ofC(N,m - 1).
2. If  (that is, a solution does in fact contain S_m), then we are using at least one S_m, thus we are now solving the subproblem of N - S_m, . This is C(N - S_m,m).

Thus, we can formulate the following:

C(N,m) = C(N,m - 1) + C(N - S_m,m)

Time Complexity: O(mn)

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

{

    int i, j, x, y;

 

    // We need n+1 rows as the table is consturcted in bottom up manner using

    // the base case 0 value case (n = 0)

    int table[n+1][m];

    

    // Fill the enteries for 0 value case (n = 0)

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

        table[0][i] = 1;

 

    // Fill rest of the table enteries in bottom up manner 

    for (i = 1; i < n+1; i++)

    {

        for (j = 0; j < m; j++)

        {

            // Count of solutions including S[j]

            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

 

            // Count of solutions excluding S[j]

            y = (j >= 1)? table[i][j-1]: 0;

 

            // total count

            table[i][j] = x + y;

        }

    }

    return table[n][m-1];

}

Following is a simplified version of method 2. The auxiliary space required here is O(n) only.

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]; }

Also refer to http://www.algorithmist.com/index.php/Coin_Change
Read full article from Dynamic Programming | Set 7 (Coin Change) | GeeksforGeeks