1
$\begingroup$

Problem: given a set of n coins of unique face values, and a value change, find number of ways of making change for change.

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
$\endgroup$
  • $\begingroup$ Try to understand the meaning of each cell in the dynamic programming table. $\endgroup$ – Yuval Filmus Jan 19 at 10:17
  • $\begingroup$ @YuvalFilmus that clears it up. Why didn't I think of that? $\endgroup$ – Abhijit Sarkar Jan 19 at 10:40
1
$\begingroup$

OP here, answering my own question for the greater good of mankind.

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.

Coin Change Problem with Repetition

dp[i - xs[j - 1]][j] + // 1
    dp[i][j - 1]       // 2
  1. Use coin j, and since there is no constraint on the denominations, solve the smaller subproblem using the same denomination.

  2. Don't use coin j.

Coin Change Problem without Repetition

dp[i - xs[j - 1]][j - 1] + // 1
    dp[i][j - 1]           // 2
  1. Use coin j, and since we used coin j for this subproblem, we can't use it for any other.
  2. Don't use coin j.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.