Рекурсивной функция итерационных

Question

Следующая функция Дана:

T(n, 0) = n, n >= 0, 
    T(0, k) = k, k >= 0, 
    T(n, k) = T(n - 1, k - 1) + T(n, k - 1) + 1, n > 0 and k > 0 

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

У вас есть несколько советов?

Answer 1

Для расчета T(n, k) вы можете использовать следующий итерационный подход:

• S (I) представляет собой вектор с Т (0, я) к Т (п, я)
• Инициализировать свой вектор состояния S (0) с нулями
• для я = 1 до к
• Вычислить S (I) с использованием S (I-1)
• ENDFOR
• Ваш результат является последним элементом S (I)

Обратите внимание, что вам нужен только последний S (i), для эффективности памяти вы можете хранить только его.