рекуррентное соотношение для перемешивающих чисел второго рода

Question

Я решал рекуррентное соотношение для перемешивающих чисел второго рода. * Метод замены 1001 *

        S(n, k)                   if
-----------------------------------------
           1                  k=1 or k=n              
           0                  k=0 or k>n    
k*S(n-1, k) + S(n-1, k-1)     otherwise

здесь не работает, потому что каждый раз, когда изменяется значение k, кто-нибудь может сказать мне, какой метод будет правильным для этого,Я просто хочу вычислить сложность времени.

Answer 1

Если вы напишите рекурсивный код, сложность по времени будет O (2 ⁿ / (sqrt (n)). Но эта проблема также может быть решена динамическим программированием, которое будет принимать O (n * k)время.