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

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)，如果 1

k＜

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);
}

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];

Answer 2

你的方法很好，除了你似乎犯了一个简单的索引错误。如果您考虑一下索引 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] 包含 S(0+j, 0)，因此它这就是你的问题所在。如果将 i 的起始值从 1 更改为 2，一切都应该没问题（对于边缘情况，您可能需要一个或两个 if） 。初始的 i=2 会将 arr[j] 从 S(1+j, 1) 转换为 S(2+j , 2)，其余的转换就可以了。

或者，您可以将 arr[j] 初始化为 S(0+j, 0)（如果已定义），但不幸的是，Stirling 的数字在 k 处未定义=0。

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