Динамическое программирование

1. Динамическое программирование

2.

Дейкстра?
Полный перебор?
Динамическое
программирование?

3.

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

4.

5.

Задача о брахистохроне Задача заключается в
нахождении кривой, соединяющей заданные точки A и B,
при движении по которой материальная точка скатится из
точки A в точку B за кратчайшее время (трением и
сопротивлением среды пренебречь).

6.

7.

Динамическое программирование
алгоритмы состоят из следующих действий:
1.Определение подзадач. Обычно на каждом шаге есть выбор между двумя
меньшими подзадачами.
2.Составление рекуррентного отношения.
3.Определение порядка выполнения подзадач. Часто бывает полезно
нарисовать одномерный или двумерный график зависимостей.
4.Реализация рекуррентного отношения, решение подзадач по порядку с
сохранением только нужных результатов и использованием мемоизации.