想知道有多少种方法可以在硬币兑换中求和？
Finding number of ways to make a sum in coin changing?
给定一个值 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.
现在，我有一个疑问。为什么我们不能做类似的事情，
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
基本上，arr[i] 存储求和的方法数 i。我在这里给出的方法有点类似于 n stairs problem，我可以爬固定数量的楼梯，也就是说，一次爬 1 个楼梯或 2 个楼梯，我必须计算从底部到达顶部的方法总数。为什么我们不能在这个问题上使用类似的方法？
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} 不应单独计算。
Samgak 的回答解释了进行更改与一次爬楼梯 1 或 2 步有何不同：进行更改时顺序无关紧要，但爬楼梯时顺序很重要。
你可以用动态规划来做这道题，但是你需要一个更复杂的状态。令 a[i][j] 为找零 i 单位货币的方式数，仅使用前 j 面额的硬币。所以，a[0][0]=1，a[i][0] = 0 对于 i 大于 0，对于 j 大于 0，a[i][j] = a[i][j-1] + a[i-Sj][j-1] + a[i-2*Sj][j-1]+...
给定一个值 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.
现在，我有一个疑问。为什么我们不能做类似的事情，
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
基本上，arr[i] 存储求和的方法数 i。我在这里给出的方法有点类似于 n stairs problem，我可以爬固定数量的楼梯，也就是说，一次爬 1 个楼梯或 2 个楼梯，我必须计算从底部到达顶部的方法总数。为什么我们不能在这个问题上使用类似的方法？
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} 不应单独计算。
Samgak 的回答解释了进行更改与一次爬楼梯 1 或 2 步有何不同：进行更改时顺序无关紧要，但爬楼梯时顺序很重要。
你可以用动态规划来做这道题，但是你需要一个更复杂的状态。令 a[i][j] 为找零 i 单位货币的方式数，仅使用前 j 面额的硬币。所以，a[0][0]=1，a[i][0] = 0 对于 i 大于 0，对于 j 大于 0，a[i][j] = a[i][j-1] + a[i-Sj][j-1] + a[i-2*Sj][j-1]+...