Мемоизация рекурсии

Вообще говоря, до алгоритма с полиномиальным временем не так уж далеко.

Фундаментальный факт, который становится вторым критическим компонентом решения методом динамического программирования, заключается в том, что наш рекурсивный алгоритм Compute-Opt в действительности решает n + 1 разных подзадач: Compute-Opt(0), Compute-Opt(1), …, Compute-Opt(n).

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

Как устранить всю эту избыточность? Можно сохранить значение Compute-Opt в глобально-доступном месте при первом вычислении и затем просто использовать заранее вычисленное значение вместо всех будущих рекурсивных вызовов.

Метод сохранения ранее вычисленных значений называется мемоизацией (memoization). Описанная стратегия будет реализована в более «умной» процедуре M-Compute- Opt.

Процедура использует массив M [0... n]; элемент M [ j] изначально содержит «пустое» значение, но принимает значение Compute-Opt( j) после первого вычисления. Чтобы определить OPT(n), мы вызываем M-Compute-Opt(n).

M-Compute-Opt( j)

Если j = 0

Вернуть 0

Иначе Если M [ j] не пусто Вернуть M [ j]

Иначе

Определить M [ j] = max(vj + M-Compute-Opt(p( j)), M-Compute-Opt( j − 1))

Вернуть M [ j]