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

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 面额被忽略。