What Are the Ideas Behind Variations of the Coin Change Problem?

Question

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

Answer 1

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.