Подход динамического программирования аналогичен принципу «разделяй и властвуй», разбивая проблему на более мелкие и все же меньшие возможные подзадачи. Но в отличие, разделяй и властвуй, эти подзадачи не решаются независимо. Скорее, результаты этих меньших подзадач запоминаются и используются для аналогичных или перекрывающихся подзадач.
Динамическое программирование используется там, где у нас есть проблемы, которые можно разделить на аналогичные подзадачи, чтобы их результаты можно было использовать повторно. В основном, эти алгоритмы используются для оптимизации. Прежде чем решить подзадачу, находящуюся в руках, динамический алгоритм попытается изучить результаты ранее решенных подзадач. Решения подзадач объединяются для достижения наилучшего решения.
Таким образом, мы можем сказать, что —
-
Проблему можно разделить на меньшую перекрывающуюся подзадачу.
-
Оптимальное решение может быть достигнуто путем использования оптимального решения небольших подзадач.
-
Динамические алгоритмы используют Memoization.
Проблему можно разделить на меньшую перекрывающуюся подзадачу.
Оптимальное решение может быть достигнуто путем использования оптимального решения небольших подзадач.
Динамические алгоритмы используют Memoization.
сравнение
В отличие от жадных алгоритмов, где применяется локальная оптимизация, динамические алгоритмы мотивированы для общей оптимизации проблемы.
В отличие от алгоритмов «разделяй и властвуй», где решения объединяются для достижения общего решения, динамические алгоритмы используют выходные данные меньшей подзадачи, а затем пытаются оптимизировать большую подзадачу. Динамические алгоритмы используют Memoization для запоминания результатов уже решенных подзадач.
пример
Следующие проблемы с компьютером могут быть решены с использованием подхода динамического программирования —
- Числовой ряд Фибоначчи
- Проблема с рюкзаком
- Ханойская башня
- Все пары кратчайшего пути по Флойд-Варшалл
- Кратчайший путь Дейкстры
- Планирование проекта
Динамическое программирование может использоваться как сверху вниз, так и снизу вверх. И, конечно же, в большинстве случаев обращение к выходным данным предыдущего решения обходится дешевле, чем пересчет с точки зрения циклов ЦП.