17

假设 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。

还有其他动态规划解决方案吗？

4

6 回答 6

9

试试这个递归函数：

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 后对其进行缓存，并在评估之前检查该值是否已存在于缓存中。

于 2011-01-03T21:19:07.770 回答
6

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

这些数字是单纯形数字。

如果要计算它们，请使用 log gamma 函数或任意精度算术。

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

于 2011-01-03T21:25:05.213 回答
5

我有我自己的公式。我们和我的朋友 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 的数字相加。

（注：加数仅为正数。）

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

于 2012-08-16T13:13:30.843 回答
3

这可以通过以下方式计算O(s+n) （或者O(1)如果您不介意近似值）：

想象一下，我们有一个带有n-1X 和so 的字符串。因此，对于您的 s=5，n=3 示例，一个示例字符串是

oXooXoo

请注意，X 将 o 分为三个不同的组：长度 1、长度 2 和长度 2 之一。这对应于 <1,2,2> 的解决方案。每个可能的字符串都为我们提供了不同的解决方案，通过计算一行中 o 的数量（可能为 0：例如，XoooooX对应于 <0,5,0>）。因此，通过计算这种形式的可能字符串的数量，我们得到了您问题的答案。

o有s+(n-1)位置可供选择s，所以答案是Choose(s+n-1, s)。

于 2012-04-06T16:02:21.720 回答
1

有一个固定的公式可以找到答案。如果您想找到将 N 作为 R 元素之和的方法数。答案总是：(N+R-1)!/((R-1)!*(N)!) 或者换句话说：(N+R-1) C (R-1)

于 2013-02-25T13:25:33.077 回答
0

这实际上看起来很像河内塔问题，没有将磁盘仅堆叠在较大磁盘上的限制。您有 S 个磁盘，可以在 N 个塔上任意组合。所以这就是让我思考它的原因。

我怀疑我们可以推导出一个不需要递归编程的公式。不过我还需要一点时间。

于 2011-01-03T21:43:11.957 回答