Структуры данных - динамическое программирование

Подход динамического программирования аналогичен принципу «разделяй и властвуй», разбивая проблему на более мелкие и, тем не менее, возможные подзадачи. Но в отличие, разделяй и властвуй, эти подзадачи не решаются независимо. Скорее, результаты этих меньших подзадач запоминаются и используются для аналогичных или перекрывающихся подзадач.

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

Таким образом, мы можем сказать, что -

  • Проблему можно разделить на меньшую перекрывающуюся подзадачу.

  • Оптимальное решение может быть достигнуто путем использования оптимального решения небольших подзадач.

  • Динамические алгоритмы используют Memoization.

сравнение

В отличие от жадных алгоритмов, где применяется локальная оптимизация, динамические алгоритмы мотивированы для общей оптимизации проблемы.

В отличие от алгоритмов «разделяй и властвуй», где решения объединяются для достижения общего решения, динамические алгоритмы используют выходные данные меньшей подзадачи, а затем пытаются оптимизировать большую подзадачу. Динамические алгоритмы используют Memoization для запоминания результатов уже решенных подзадач.

пример

Следующие проблемы с компьютером могут быть решены с использованием подхода динамического программирования -

  • Числовая серия Фибоначчи
  • Проблема с рюкзаком
  • Ханойская башня
  • Все пары кратчайшего пути по Флойд-Варшалл
  • Кратчайший путь Дейкстры
  • Планирование проекта

Динамическое программирование может использоваться как сверху вниз, так и снизу вверх. И, конечно же, в большинстве случаев обращение к выходным данным предыдущего решения обходится дешевле, чем пересчет с точки зрения циклов ЦП.