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

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

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

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), если бы он был определен, но, к сожалению, числа Стерлинга не определены в k=0.

РЕДАКТИРОВАТЬ: Очевидно, я был неправ в моем последнем комментарии. Если вы инициализируете arr в {1, 0, 0, ...}, вы можете оставить начальное значение i как 1. Для этого вместо него используются начальные значения S(0, 0)=1 и S(n, 0)=0, n>0.