Динамическое программирование — это в основном оптимизация простой рекурсии. Везде, где мы видим рекурсивное решение, которое имеет повторяющиеся вызовы для одних и тех же входов, мы можем оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы просто сохранить результаты подзадач, чтобы нам не приходилось повторно вычислять их, когда это понадобится позже. Эта простая оптимизация сокращает временные сложности от экспоненциального до полиномиального. Например, если мы напишем простое рекурсивное решение для чисел Фибоначчи, мы получим экспоненциальную временную сложность, а если мы оптимизируем его, сохранив решения подзадач, временная сложность уменьшится до линейной.
Числа Фибоначчи
Числа Фибоначчи — это числа следующей целочисленной последовательности:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Строго математически, эти числа определяются с помощью рекуррентного соотношения
с начальными значениями
Задача
Для заданного натурального числа n выведите n-ый член последовательности Фибоначчи.
Примеры
Вход : 2 Выход : 1 Вход : 9 Выход : 34
Рекурсивный метод
Простой метод, который использует математическое рекурсивное определение.
Вывод программы:
34
Мы можем заметить, что эта реализация выполняет много повторяющейся работы (см. следующее дерево рекурсии), поэтому это плохой метод для нахождения n-го числа Фибоначчи.
Метод динамического программирования
Используя данный способ решения, мы можем избежать повторения работы, которое возникло при использовании рекурсивного метода, сохранив рассчитанные на данный момент числа Фибоначчи.
Вывод программы:
34
В этом методе вычислительная сложность будет линейной, в отличие от предыдущего метода, в котором экспоненциальная сложность.