Optimized space for changing coins

Question

Given the value of N, if we want to make changes for N cents, and we have an infinite supply of each of S = {S1, S2, ..., Sm} valuable coins, how many ways can we make a change? The order of the coins does not 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 }. Thus, the 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 3 approaches HERE . But it is not able to understand the space-optimized approach to dynamic programming, where only the one-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[jS[i]]; return table[n]; } 

Answer 1

First, note that table [i] is the number of ways to change a coin when N = i.

This algorithm fills this array (table []) according to a given set of coins (S []). Initially, all values ​​in table [] are initialized to 0. And table [0] is set to 0 (this is the base case N = 0).

Each coin adds values ​​to table [] as follows.

For a coin of value X, the following updates in the table [] -

• table [X] = table [X] + 1

  This is easy to understand. In particular, this adds the solution {X}.

• for all Y> X

  table [Y] = table [Y] + table [YX]

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

  4 = 3 + 1, that is, 4 can be obtained by combining 3 and 1. And by definition, the number of ways to get 1 is the table [1]. So many methods have been added to table [4]. This is why the expression above uses the table [YX].

The next line in your algorithm represents the same thing (above two steps) -

 table[j] += table[jS[i]]; 

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

Answer 2

Try to understand the algorithm using this method.

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

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

Clearly, when creating coins j , you have two options. not using the i-th coin or using the i-th coin. When the ith coin is not used, the solution number is table[i-1][j] . When using the i-th coin, the solution number is table[i][jS[i]] , which means using the first i coins to create the value jS [i]. Therefore, the sum is the sum of both, which is table[i-1][j] + table[i][jS[i]]

In the code, you will see a for loop. the outer loop iterates over i and the inner loop repeats over j. the += operator computes table[i][j] based on the equation above.

EDIT

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

I will talk in more detail based on the code:

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

When i = 0 , table[j] means using the first 1 coins to make changes to the j value. for example, table[2] now means using coins {1} to change to 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 changes for values ​​1, 2, 3, 4 separately.

When i = 1, table[j] means using coin {1, 2} to make changes to the value of 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 next process is the same.

Finally, we take table[4] when i = 1 exit 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 that 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 can expand to:

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

equation for sure

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

EDIT Follow up question

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

Hint: just one change to the source code is enough.

Answer: http://ideone.com/t1JnEz

Answer 3

I will try to explain it to 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 quite simple, without space optimization. At first, we might think that we only get access to information from the column index j - 1 , so we can drop the columns, but this is not so, since we also refer to dp[i - coins[j]][j] . Therefore, the information contained in the j'th index is useful, and we cannot delete 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 we did was reorder the for loops. Watching carefully, we see that dp[i][j-coins[i]] is in the same row as dp[i][j] . Does this mean that we do not need to store information from other lines? Yes we are not

Now there are two ways to do this: either support two arrays, one for dp[i] , the other for dp[i-1] , or discard the row index altogether, which will cause all data to accumulate in dp[j] for all values ​​of i . ].

The code for the second approach is

 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]