c++ - 想知道有多少种方法可以在硬币兑换中求和？

Question

给定一个值 N，如果我们想找零 N 美分，并且我们有无限供应的每个 S = { S1, S2, .. , Sm} 值(value)的硬币，我们有多少种找零的方法？硬币的顺序无关紧要。

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

现在，我有一个疑问。为什么我们不能做类似的事情，

arr[i] = arr[i-1] + arr[i-2] + arr[i-3]

基本上，arr[i] 存储求和 i 的方法数。我在这里给出的方法有点类似于n stairs problem，即我可以爬固定数量的楼梯，也就是说，一次爬 1 个楼梯或一次爬 2 个楼梯，并且我必须计算从底部到达顶部的方法总数。为什么我们不能在这个问题上使用类似的方法？

Answer 1

Why can't we use a similar approach in this question?

这是行不通的，因为在 n 阶梯问题中，顺序很重要。例如如果您要爬 5 个楼梯，则 {1, 2, 1, 1} 被视为与 {1, 1, 2, 1} 不同。

然而，在找零的问题中，只有每个硬币的总数，而不是你添加它们的顺序，所以如果你赚 5 美元，{$1, $2, $1, $1} 与 {$1, $1, 2 美元，1 美元}。因此，简单的内存方法不起作用，您需要存储到达 arr[i] 的所有可能方式，而不仅仅是总数。

例如，假设您尝试用 1 美元和 2 美元赚取 6 美元。您不能只将赚取 4 美元的方式的数量添加到赚取 5 美元的方式的数量，因为(例如)赚取 4 美元的方式之一是 {$1, $1, $2}(您可以将 $2 添加到赚取 6 美元，即 {$1, $1, $2, $2})，赚取 5 美元的方法之一是 {$1, $2, $2}(您可以添加 $1 来赚取 $6 {$1, $2, $2, $1}) .

然而，{$1, $2, $2, $1} 和 {$1, $1, $2, $2} 不应单独计算。