Динамическое программирование
Динамическое программирования — стратегия (подход) для решения задач при котором задача решается через последовательность более простых задач. Результате полученные в более простых задачах используются для решения более сложных. Каждая подзадача должна быть автономна и не зависеть от других задач.
Динамическое программирование применяется для оптимизации какой-либо характеристики. Для решения задачи строиться таблица. Значения ячеек таблицы соответствуют оптимизируемой характеристике. Для заполнения ячейки необходимо решить подзадачу.
Примеры задач:
- Задача о рюкзаке
- Нахождение различий между двумя строками или файлами (diff)
- Алгоритм переноса строк в текстовых редакторах, для сохранения одинаковой длины строк
Ссылки
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 9. Динамическое программирование