与N个数相加的和S的方法数

Question

假设S = 5且N = 3,解决方案看起来像 - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> < 2,3,0> <3,2,0> <1,2,2>等

在一般情况下,N个嵌套循环可用于解决问题.运行N嵌套循环,在它们内部检查循环变量是否加到S.

如果我们提前不知道N,我们可以使用递归解决方案.在每个级别中,运行从0到N的循环,然后再次调用函数本身.当我们达到N的深度时,看看获得的数字是否加起来为S.

其他动态编程解决方案？

Answer 1

试试这个递归函数:

f(s, n) = 1                                    if s = 0
        = 0                                    if s != 0 and n = 0
        = sum f(s - i, n - 1) over i in [0, s] otherwise

要使用动态编程,您可以在评估后缓存f的值,并在评估之前检查缓存中是否已存在该值.

Answer 2

有一个封闭形式公式:二项式(s + n - 1,n)

这些数字是单数.

如果要计算它们,请使用log gamma函数或任意精度算法.

请参阅https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers

Answer 3

我对此有自己的公式。我们和我的朋友Gio一起对此进行了调查报告。我们得到的公式是[2 raised to (n-1) - 1]，其中n是我们要寻找的具有多少加数的数字。

我们试试吧。

• 如果n为1：其加数为o。没有两个或两个以上的数字可以加总为1（不包括0）。让我们尝试一个更大的数字。
• 让我们尝试4 4 has addends: 1+1+1+1, 1+2+1, 1+1+2, 2+1+1, 1+3, 2+2, 3+1。总计为7。 让我们检查一下公式。2升到（4-1）-1 = 2升到（3）-1 = 8-1 = 7。
• 让我们尝试15。2升到（15-1）-1 = 2升到（14）-1 = 16384-1 =16383。因此，有16383种方法来添加等于15的数字。

（注意：加数仅是正数。）

（您可以尝试其他数字，以检查我们的公式是否正确。）