Problem: given a set of
ncoins of unique face values, and a valuechange, find number of ways of making change forchange.
Assuming we can use a denomination more than once, here's the pseudocode I came up with
1. NUM-WAYS(denom[], n, change)
2. dp = [change + 1][n + 1]
3. for i = 0 to n
4 dp[i][0] = 1
5. xs = denom.sorted
6. for i = 1 to change
7. for j = 1 to n
8. if xs[j - 1] > i
9. dp[i][j] = dp[i][j - 1]
10. else
11. dp[i][j] = dp[i - xs[j - 1]][j] + dp[i][j - 1]
12. return dp[change][n]
The above algorithm is clear to me. However, if we are only allowed to use a denomination once, then line 11 changes to dp[i - xs[j - 1]][j - 1] + dp[i][j - 1], as if we are not allowed to use the current denomination at all. I'm failing to wrap my head around this. Can you explain this?
Here're some test runs:
Change: 3, denominations: [8, 3, 1, 2]
11111
01111
01222
01233
// use once
Change: 3, denominations: [8, 3, 1, 2]
11111
01111
00111
00122
Change: 4, denominations: [3, 1, 2]
1111
0111
0122
0123
0134
// use once
Change: 4, denominations: [3, 1, 2]
1111
0111
0011
0012
0001
Let dp[i][j] denote the solution to the [i, j]-th subproblem; that is,
dp[i][j] is the number of ways to make change for the amount i, using coins j through n.
j-th denomination was taken. Since there's no constraint on the denominations, j may remain the same so it can be used again for smaller subproblems: dp[i - xs[j - 1]][j].It's the same as the above problem with an additional constraint that a coin of some denomination can be only taken once.
j-th denomination was taken. Since we can't use denomination j anymore, j changes to j-1: dp[i - xs[j - 1]][j - 1]The second case is the same in both problems where the j-th denomination is ignored.