Информатика • 11 класс

Динамическое программирование как метод решения задач с сохранением промежуточных результатов (Python)

Динамическое программирование (ДП) – метод решения задач путём разбиения на перекрывающиеся подзадачи, с сохранением результатов их решения для повторного использования (мемоизация).
Основные принципы:
- оптимальная подструктура – решение задачи можно получить из решений подзадач;
- перекрывающиеся подзадачи – одни и те же подзадачи решаются многократно;
- мемоизация – сохранение результатов вычислений для избежания повторов.
Пример. Числа Фибоначчи
n = int (input ("Введите n: "))
fib = [0] * 101
fib [1] = 1
fib [2] = 1
for i in range (3, n + 1):
fib [i] = fib [i - 1] + fib [i - 2]
print (fib [n])

Было полезно?