Динамическое программирование — это в основном оптимизация простой рекурсии. Везде, где мы видим рекурсивное решение, которое имеет повторяющиеся вызовы для одних и тех же входов, мы можем оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы просто сохранить результаты подзадач, чтобы нам не приходилось повторно вычислять их, когда это понадобится позже. Эта простая оптимизация сокращает временные сложности от экспоненциального до полиномиального. Например, если мы напишем простое рекурсивное решение для чисел Фибоначчи, мы получим экспоненциальную временную сложность, а если мы оптимизируем его, сохранив решения подзадач, временная сложность уменьшится до линейной.

Числа Фибоначчи

Числа Фибоначчи — это числа следующей целочисленной последовательности:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Строго математически, эти числа определяются с помощью рекуррентного соотношения

Динамическое программирование. Основы, изображение №1

с начальными значениями

Динамическое программирование. Основы, изображение №2

Задача

Для заданного натурального числа n выведите n-ый член последовательности Фибоначчи.

Примеры

Вход  : 2
Выход : 1

Вход  : 9
Выход : 34

Рекурсивный метод

Простой метод, который использует математическое рекурсивное определение.

Рекурсивная реализация на C++
Рекурсивная реализация на C++

Вывод программы:

34

Мы можем заметить, что эта реализация выполняет много повторяющейся работы (см. следующее дерево рекурсии), поэтому это плохой метод для нахождения n-го числа Фибоначчи.

Дерево рекурсии
Дерево рекурсии

Метод динамического программирования

Используя данный способ решения, мы можем избежать повторения работы, которое возникло при использовании рекурсивного метода, сохранив рассчитанные на данный момент числа Фибоначчи.

Реализация динамического программирования на C++
Реализация динамического программирования на C++

Вывод программы:

34

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

Источник

Контакты

Напишите нам — мы всегда будем рады ответить