c++ - 计算斯特林数的动态规划方法

Question

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), if 1 < k < n

S(n,k) = 1, if k=1 ou 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);
}

Answer 1

发现错误。 您已经计算了 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];