数量N的更改方式的数量 [英] Number of ways to make change for amount N

问题描述

我遇到了这个问题：

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

给定一个值N，如果我们想找零N分钱，并且我们有无限数量的S = {S1，S2，..，Sm}值的硬币，我们可以用几种方法制造改变？硬币的顺序无关紧要。

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.

例如，对于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。

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];
}

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

But this counts duplicates which have the same denominations but in different order. For example, if denominations = {1,2} and N=3, then it counts {1,1,1}, {2,1}, {1,2} which has duplicate entry {1,2}.

我看到链接此处避免重复。我了解递归关系的工作原理以及所有其他方面，但我无法理解，而我的解决方案却无法避免重复关系。请解释背后的想法。

I see that the DP solution described in the link here avoids duplicates. I understand how the recurrence relation works and all but I am not able to understand how it is able to avoid the duplicates while my solution is not. Please explain the idea behind.

推荐答案

让 C（i，j）使用面额 S1，...，Sj 的硬币制作总 i 的方法数量。您的代码实现以下重复发生（有序方式）。

Let C(i, j) the number of ways to make the total i using coins of denominations S1, ..., Sj. Your code implements the following recurrence (ordered ways).

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 的所有条款，但链接的代码添加了<$每个 i 的c $ c> j 项，然后是 j + 1 的项结果，当链接代码考虑使用面额- Sj 硬币的可能性时，小计 i ，它隐含地仅考虑那些以面额 S1，...，Sj 的硬币继续的解决方案，因为当前 i-Sj 的总数不包括使用其他硬币的可能性。

The difference between the two codes is subtle: more or less just how the loops are nested. Yours adds all of the terms for i before moving on to i + 1, but the linked code adds the j term for each i, then the j + 1 term for each i, etc. As a result, when the linked code considers the possibility of using a denomination-Sj coin from subtotal i, it implicitly is considering only those solutions that continue with coins of denominations S1, ..., Sj, because the current total for i - Sj does not include the possibilities that use other coins.

这篇关于数量N的更改方式的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！