金额N的变更方式

Question

我遇到了这个问题:

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

给定值N,如果我们想要改变N美分,并且我们每个S = {S1,S2,..,Sm}值硬币都有无限供应,我们可以通过多少方式进行更改？硬币的顺序无关紧要.

例如,对于N = 4和S = {1,2,3},有四个解:{1,1,1,1},{1,1,2},{2,2},{1, 3}.因此输出应为4.对于N = 10且S = {2,5,3,6},有五种解决方案:{2,2,2,2,2},{2,2,3,3}, {2,2,6},{2,3,5}和{5,5}.所以输出应该是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];
}

但这会计算具有相同面额但顺序不同的重复项.例如,如果面额= {1,2}且N = 3,则计数{1,1,1},{2,1},{1,2}具有重复的条目{1,2}.

我看到,在链接中描述的DP解决方案在这里避免了重复.我理解递归关系是如何工作的,但除了我的解决方案之外,我无法理解它是如何能够避免重复的.请解释背后的想法.

Answer 1

让使用面额硬币C(i, j)的总数的i方法S1, ..., Sj.您的代码实现了以下重复(有序方式).

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在移动到前i + 1,但链接代码添加j术语对于每个i,那么j + 1术语的每个i等.作为结果,当链接的代码认为使用denomination-的可能性Sj硬币从小计i,它隐含地只考虑那些继续使用面额硬币的解决方案S1, ..., Sj,因为当前的总数i - Sj不包括使用其他硬币的可能性.