algorithm - 找零的方式数 N

Question

我遇到了这个问题:

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

我想到了解决方案:

// recurrence relation
count[N] = count[N-d] for all denomination <= N

Source code
-----------

public static int numWays(int N, int[] denoms) {
  if (N == 0)
     return 0;
  
  int[] ways = new int[N+1];
  ways[0] = 1;
  
  for (int i=1; i<=N; i++) {
     ways[i] = 0;
     for (int d : denoms) {
        if (d <= i) {
           ways[i] += ways[i-d];
        }
     }
  }
  
  return ways[N];
}

但这会计算面额相同但顺序不同的重复项。例如，如果 denominations = {1,2} 且 N=3，则它计算 {1,1,1}、{2,1}、{1,2} 其中有重复条目 {1,2}。

我看到链接中描述的 DP 解决方案 here避免重复。我理解递归关系是如何工作的，但我无法理解它是如何避免重复的，而我的解决方案却没有。请解释背后的想法。

Answer 1

设 C(i, j) 是使用面额为 S1, ..., Sj 的硬币使总数 i 的方法数>。您的代码实现了以下循环(有序方式)。

C(i, m) | i <  0 = 0
        | i == 0 = 1
        | i >  0 = sum_{j = 1}^m C(i - Sj, m)

链接代码实现了不同的循环(无序方式)。

C(i, j) | i <  0           = 0
        | i == 0           = 1
        | i >  0 && j <= 0 = 0
        | i >  0 && j >  0 = C(i - Sj, j) + C(i, j - 1)

这两个代码之间的区别很微妙:或多或少只是循环的嵌套方式。在继续 i + 1 之前，您添加了 i 的所有术语，但是链接代码为每个 添加了 j 术语i，然后是每个 i 的 j + 1 项，等等。因此，当链接代码考虑使用面额的可能性时 - Sj coin from subtotal i，它隐含地只考虑那些继续使用面额硬币 S1, ..., Sj 的解决方案，因为当前总数对于 i - Sj 不包括使用其他硬币的可能性。