CODEWITHSUNDEEP
algorithmdynamic-programming
d125q
d125q

Reputation: 1666

In how many ways can a change be made if the order in which the coins are paid matters?

I am considering a variation of this problem: given a list of denominations S and a change amount n, in how many ways can we make the change if the order in which the coins are paid matters?

For example, if S = {1,2} and n = 4, then the result should be 5, as (1,2,1), (1,1,2), (2,1,1), (1,1,1,1) and (2,2) are all possible solutions. Solving this where the order doesn't matter is easy, but I got stuck in this case.

Consider the code given here:

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

When we have this line, x = (i-S[j] >= 0)? table[i - S[j]][j]: 0, how would I know how many solutions the addition of a new coin gives me?

Upvotes: 1

Views: 206

Answers (2)

d125q
d125q

Reputation: 1666

This turned out to be closely related to the Fibonacci numbers. A solution is a very simple modification to the code given in my original post.

All that has to be done is have this line:

// Count of solutions including S[j]
x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

changed to

// Count of solutions including S[j], but taking all "m" coins into account
x = (i-S[j] >= 0)? table[i - S[j]][m - 1]: 0;

This problem was apparently even discussed previously at StackOverflow.

Upvotes: 0

Terry Storm
Terry Storm

Reputation: 497

For just generating the number : i refer to jpmath's comment.

for learning DP sake only :

easiest adaptation would be to extend the table with one dimension.

table[i][j][k] would then be whatever table[i][j] means (probably j = number coins and i = sum) with last coin being k.

in each step iterate through every coin >= k and add all necessary.

As dynamic programming always includes reasonable bounds it would be an easy adaptation with moderately slower running time. However as the Set S should be small either way it shouldnt be a problem.

Upvotes: 2

Related Questions