Школа №1 Остров

Динамическое программирование — метод решения задачи путём разбиения её на меньшие подзадачи, которые имеют такую же структуру. Для того чтобы задача решалась методом динамического программирования, она должна обладать следующими свойствами:

*оптимальная подструктура (оптимальное решение задачи может быть составлено из оптимальных решений ее подзадач) *пересекающиеся подзадачи (одна и та же подзадача нужна для решения большого количества других подзадач) *возможность мемоизации (ограничения на память позволяют запоминать ответы на все решённые подзадачи)

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

Рекурсивные методы решения задач, как правило, производят полный перебор всех вариантов. Динамическое программирование также производит полный перебор всех вариантов, но делает это оптимизированно за счёт мемоизации (каждая подзадача решается только один раз и её решение сохраняется).

Задача. Нахождение N-го числа Фибоначчи. Числа Фибоначчи — это ряд чисел, который определён первыми двумя членами F0=0, F1=1 и рекуррентным соотношением FN=FN−1+FN−2, N≥2. Можно выписать несколько первых членов этого ряда:

Реализация такого алгоритма для n>0

имеет следующий вид:

n = int(input())
f = [-1] * (n + 1)
f[0] = 0
f[1] = 1
for i in range (2, n + 1):
    f[i] = f[i - 1] + f[i - 2]