1

我在这里遇到了 Coin Change 问题的解决方案：Coin Change。在这里，我能够理解第一种递归方法，第二种方法使用 DP 和 2D 数组。但我无法理解第三种解决方案背后的逻辑。

据我所知，最后一种方法适用于考虑硬币兑换中使用的硬币顺序的问题。我对么？如果我错了，谁能解释我。

4

2 回答 2

1

好吧，我自己想通了！

使用归纳法可以很容易地证明这一点。令 table[k] 表示总共 k 的变化方式。现在该算法由两个循环组成，一个由 i 控制并遍历包含所有不同硬币的数组，另一个是 j 控制循环，对于给定的 i，更新数组表中元素的所有值。现在考虑对于一个固定的 i，我们已经计算了可以为从 1 到 n 的所有值给出变化的方式的数量，这些值存储在从 table[1] 到 table[n] 的表中。当 i 控制循环迭代 i+1 时，table[j] 中任意 j 的值会增加 table[jS[i + 1]]，这不过是我们可以使用至少一个硬币创建 j 的方法value S[i + 1]（存储硬币值的数组）。因此，table[j] 中的总价值等于我们可以使用价值 S[1]....S[i] 的硬币（之前已经存储）和价值 table[jS[i + 1]]。这与递归算法中使用的问题的最优子结构相同。

于 2015-11-20T09:27:13.507 回答
0 
int arr[size];
memset(arr,0,sizeof(size));
int n;
cin>>n;
int sum;
cin>>sum;
int a[size];
fi(i,n)
cin>>a[i];
arr[0]=1;
fi(i,n)
for(int j=arr[i]; j<=n; j++)
    a[j]+=a[j-arr[i]];
cout<<arr[n];

该数组arr被初始化为 0，以表明i可以表示总和的方式数为零（即未初始化）。但是，可以表示 0 和的方式的数量是 1（零方式）。此外，我们取出每个硬币并从硬币面额开始初始化数组中的每个位置。 a[j]+=a[j-arr[i]]意味着我们基本上是j通过前面的方式数来增加表示总和的可能方式，required ( j-arr[i])。最后，我们输出a[n]

于 2016-02-14T08:16:24.123 回答