假设 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。
还有其他动态编程解决方案吗?
假设 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。
还有其他动态编程解决方案吗?
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之后缓存其值,并在评估之前检查该值是否已存在于缓存中。
有一个封闭形式的公式:二项式(s + n - 1, s)或二项式(s+n-1,n-1)
这些数字是单纯形数。
如果你想计算它们,可以使用对数伽玛函数或任意精度算术。
参见https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers
O(s + n)
(如果您不介意使用近似值),则可以计算为O(1)
。
假设我们有一个字符串,其中包含n-1
个X和s
个o。例如,对于您的示例,当时,一个示例字符串如下:oXooXoo
XoooooX
将对应于<0,5,0>)。因此,通过计算这种形式的可能字符串的数量,我们可以得到您问题的答案。s+(n-1)
个位置可供选择s
o,因此答案是Choose(s+n-1, s)
。这实际上看起来很像汉诺塔问题,但没有只能在较大的盘子上叠放盘子的限制。您有S个盘子,可以以任何组合放置在N个塔上。这就是让我开始思考它的原因。
我怀疑我们可以推导出一个公式,而不需要递归编程。不过我还需要一点时间。