Подход динамического программирования к вычислению числа Стирлинга

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

S (n, k) = 1, если 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);
}