Geek Answers Handbook

Dynamic programming method for calculating the Stirling number

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

Here is my attempt to determine Stirling numbers using dynamic programming.

It is defined as follows:

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

Seems good, right? Except when I run my unit test ...

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

Can anyone see what I'm doing wrong?

Thank!

BTW, here's a recursive solution:

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);
}
+5
source share
2 answers

. k = 1 (S (n, 1) = 1 n). 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];
+4

, , , , . , i j , arr[j] , ( , , , :.))

, , i k , arr[j] S(i+j, i-1) S(i+1+j, i). , arr, S(1+j, 1). . : i , arr[j] S(0+j, 0), . i 1 2, ( if two ). i=2 arr[j] S(1+j, 1) S(2+j, 2), .

arr[j] S(0+j, 0), , , , undefined at k=0.

EDIT: -, . arr {1, 0, 0,...}, i 1. S(0, 0)=1 S(n, 0)=0, n>0.

+3

More articles:


All Articles