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

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

• Try to understand the meaning of each cell in the dynamic programming table. – Yuval Filmus Jan 19 at 10:17
• @YuvalFilmus that clears it up. Why didn't I think of that? – Abhijit Sarkar Jan 19 at 10:40

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.