5 
int s_dynamic(int n,int k) {
    int maxj = n-k;

    int *arr = new int[maxj+1];

    for (int i = 0; i <= maxj; ++i)
        arr[i] = 1;

    for (int i = 1; i <= k; ++i)
        for(int j = 1; j <= maxj; ++j)
            arr[j] += i*arr[j-1];

    return arr[maxj];
}

这是我使用动态规划确定斯特林数的尝试。

定义如下：

S(n,k) = S(n-1,k-1) + k S(n-1,k)，如果 1 < k < n

S(n,k) = 1，如果 k=1 或者 k=n

看起来不错，对吧？除非我运行单元测试...

partitioningTest ..\src\Test.cpp:44 3025 == s_dynamic(9,3) expected:    3025    but was:    4414

谁能看到我做错了什么？

谢谢！

顺便说一句，这是递归解决方案：

int s_recursive(int n,int k) {
    if (k == 1 || k == n)
        return 1;

    return s_recursive(n-1,k-1) + k*s_recursive(n-1,k);
}
4

2 回答 2

4

发现了错误。您已经计算了 k=1 的动态斯特林数数组（对于所有 n，S(n,1)=1）。您应该开始计算 S(n,2) - 即：

for (int i = 2; i <= k; ++i) //i=2, not 1
  for(int j = 1; j <= maxj; ++j)
    arr[j] += i*arr[j-1];
于 2011-02-27T13:16:03.070 回答
3

你的方法很好，除了你似乎犯了一个简单的索引错误。如果您考虑一下索引i和j表示什么，以及内部循环转换为什么arr[j]，您会很容易看到它（我撒谎，我花了半个小时才弄清楚什么是什么:)）。

根据我可以解码的内容，i表示k计算期间的值，并arr[j]从 转换S(i+j, i-1)为S(i+1+j, i). 初始化的最顶层 for 循环arr将其设置为S(1+j, 1). 根据这些循环，计算看起来很好。除了一件事：第一个i循环假设arr[j]contains S(0+j, 0)，因此这就是您的问题所在。i如果您将from的起始值更改1为2，一切都应该没问题（对于极端情况，您可能需要一个 if 或两个）。初始i=2将转换arr[j]为S(1+j, 1)to S(2+j, 2)，其余的转换就可以了。

或者，如果已定义，您可以初始化arr[j]为S(0+j, 0)，但不幸的是，斯特林的数字未定义在k=0.

编辑：显然我在上一条评论中错了。如果将 arr 初始化为 {1, 0, 0, ...}，则可以将起始值保留i为1。为此，您使用初始值S(0, 0)=1，而S(n, 0)=0, n>0不是。

于 2011-02-27T13:18:10.957 回答