space optimized solution for 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.

I found the 3 approaches HERE. But not able to understand the space optimized dynamic programming approach where only a single dimensional array table[] is used.

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

回答1:

First note that table[i] is number of ways for coin change when N=i.

Given Algorithm fills this array (table[]) as per given set of coin (S[]). Initially all values in table[] are initialized to 0. And table[0] set to 0 (this is base case N=0).

Each coin adds up values in table[] in following manner.

For coin of value X, following are updates to table[] -

1. table[X] = table[X] + 1

   This is easy to understand. Specifically this adds solution {X}.

2. for all Y > X

   table[Y] = table[Y] + table[Y-X]

   This is tricky to understand. Take example X = 3, and consider case for Y = 4.

   4 = 3 + 1 i.e. 4 can be obtained by combining 3 and 1. And by definition number of ways to get 1 are table[1]. So that many ways are added to table[4]. Thats why above expression uses table[Y-X].

Following line in your algorithm represents the same (above two steps) -

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

At the end of algorithm, table[n] contains solution for n.

回答2:

Try to understand the algorithm using this way.

table[i][j] means using the first i types of coins to make change for value j. then:

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

Clearly when making up j coins, you have two choices. not using the ith coin or using the ith coin. When not using the ith coin, the solution number is table[i-1][j]. When using the ith coin, the solution number is table[i][j-S[i]], which means using the first i coins to make up j-S[i] value.Therefore, the total is the sum of both, which is table[i-1][j] + table[i][j-S[i]]

In the code, you will see the for loop. the outer loop iterate over i and the inner loop iterate over j. the += statement calculate table[i][j] based on the equation above.

EDIT

table[j] in your code is actually the table[i][j] I am talking above and i is the value in your loop. after the loop table[N] means table[M][N], representing using first M coins, which are all the coins, to make value for N.

I will provide more detail based on the code:

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

When i = 0, table[j] means using the first 1 coins to make changes for value j. for example, table[2] right now means using coins {1} to make change for 2. So:

table[1] = table[1] + table[1 - S[0]] = table[1] + table[0] = 1 + 0= 1
table[2] = table[2] + table[2 - S[0]] = table[2] + table[1] = 0 + 1= 1
table[3] = 1
table[4] = 1

After that, we got the results when i = 0. table[1] ~ table[4] now means using coin {1} to make change for values 1, 2, 3, 4 separately.

When i = 1, table[j] means using coin {1, 2} to make changes for value j.

table[2] = table[2] + table[2 - S[1]] = table[2] + table[0] = 1 + 1= 2
table[3] = table[3] + table[3 - S[1]] = 1 + 1 = 2
table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3

The following process is the same.

Finally, We take table[4] when i = 1 out and analyze it:

table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3

Here table[4] on the left is the value we are calculating and actually it is table[i=1][4]. table[4] on the right represents the previous value and in this case, table[i=0][4]. It could expand to:

table[i=1][4] = table[i=0][4] + table[i=1][4 - S[1]]

the equation is exactly

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

EDIT Follow-Up question

If you think you really understand this question, try to solve the same problem with a new constraint. What if every coin can only be used once? For example, N = 4 and S = {1,2,3}, only one solution {1,3} so the output should be 1. And For N = 10 and S = {2, 5, 3, 6}, still only one solution {2, 3, 5} and the output is 1.

Hint: only one line change of original code is enough.

Answer:http://ideone.com/t1JnEz

回答3:

Will try to explain it for others..

Consider this piece of code -

dp = [[0 for i in range(len(coins))] for j in range(n+1)]
for i in range(n+1):
    for j in range(len(coins)):
        if i == 0:
            dp[i][j] = 1
        elif j == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i][j-1]

        if i - coins[j] >= 0:
            dp[i][j] += dp[i-coins[j]][j]

print dp[n][len(coins)-1]

This approach is fairly basic, with no space optimisation. At first we may think that we are only accessing information from the column index j - 1 so we can drop the columns but that's not true since we're also accessing dp[i - coins[j]][j]. Therefore information contained at j'th index is useful and we cannot drop the columns.

Now consider this,

dp = [[0 for i in range(n+1)] for j in range(len(coins))]
for i in range(len(coins)):
    for j in range(n+1):
        if j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i-1][j]

        if j - coins[i] >= 0:
            dp[i][j] += dp[i][j-coins[i]]

print dp[len(coins)-1][n]

All that we've done is reversed the order of for loops. On observing carefully, we can see that dp[i][j-coins[i]] is from the same row as dp[i][j]. So does that mean we don't need to maintain information from other rows? Yes we don't.

Now there's two ways to go about this, either maintain two arrays, one for dp[i], another for dp[i-1], or drop the row index altogether which will lead to all data being accumulated at dp[j] for all values of i.

Code for the second approach -

dp = [0 for i in range(n+1)]

dp[0] = 1
for i in range(len(coins)):
    for j in range(coins[i], n+1):
        dp[j] += dp[j-coins[i]]

return dp[n]