硬币找零问题变体背后的想法是什么？

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.

假设我们可以多次使用一个面额，这是我想出的伪代码

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]

上面的算法我已经很清楚了。但是，如果我们只允许使用一次面额，那么第 11 行将变为 dp[i - xs[j - 1]][j - 1] + dp[i][j - 1]，就好像我们根本不允许使用当前面额一样。我无法解决这个问题。你能解释一下吗？

这是一些测试运行：

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

设 dp[i][j] 表示第 [i, j] 个子问题的解；那是， dp[i][j] 是使用硬币 j 到 n.

找零的方式数 i

硬币找零重复问题

• 第一种情况假设取走了第 j 面额的一枚硬币。由于对面额没有限制，j 可能保持不变，因此它可以再次用于较小的子问题：dp[i - xs[j - 1]][j].

不重复的找零问题

同上题一样，多了一个限制条件，即某种面额的硬币只能取一次

• 第一种情况假设取走了第 j 面额的一枚硬币。由于我们不能再使用面额 j，j 更改为 j-1：dp[i - xs[j - 1]][j - 1]

第二种情况在两个问题中都是相同的，第 j 个面额被忽略。