硬币兑换问题变化背后的想法是什么?

问题:给定一组 n 面值独特的硬币 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