Методы динамического программирования (ДП)

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

Выполнила: Тимошенко Таисия
Науч.Рук: Гумеров Р.

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

1. Рекурсивный метод - заключается в рекурсивном вызове функции, которая решает задачу, разбивая ее на более мелкие подзадачи. Результаты вычислений сохраняются в таблице, чтобы избежать повторных вычислений.

2. Метод заполнения таблицы - представляет собой итеративный алгоритм, который заполняет таблицу решения, начиная с наименьших подзадач и двигаясь к более сложным. Результаты сохраняются в таблице, чтобы избежать повторных вычислений.

Основные методы ДП:

3. Метод нарезки - заключается в разбиении задачи на несколько частей и решении каждой части отдельно. Результаты сохраняются в таблице, чтобы избежать повторных вычислений.

4. Метод потока - используется для решения задач на максимальный поток в графе. Он основывается на поиске пути с максимальным потоком от источника к стоку.