DAA - динамическое программирование

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

Два основных свойства проблемы предполагают, что данную проблему можно решить с помощью динамического программирования. Эти свойстваoverlapping sub-problems and optimal substructure.

Перекрывающиеся подзадачи

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

Например, у двоичного поиска нет перекрывающихся подзадач. В то время как рекурсивная программа чисел Фибоначчи имеет много перекрывающихся подзадач.

Оптимальная подструктура

Данная проблема обладает свойством оптимальной подструктуры, если оптимальное решение данной проблемы может быть получено с использованием оптимальных решений ее подзадач.

Например, задача кратчайшего пути имеет следующее свойство оптимальной подструктуры:

Если узел x лежит на кратчайшем пути от исходного узла u к узлу назначения v, то кратчайший путь из u к v это комбинация кратчайшего пути из u к x, и кратчайший путь от x к v.

Стандартные алгоритмы кратчайшего пути по всем парам, такие как Floyd-Warshall и Bellman-Ford, являются типичными примерами динамического программирования.

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

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

• Охарактеризуйте структуру оптимального решения.
• Рекурсивно определить значение оптимального решения.
• Вычислите значение оптимального решения, как правило, снизу вверх.
• Постройте оптимальное решение из вычисленной информации.

Применение подхода динамического программирования

• Умножение матричной цепочки
• Самая длинная общая подпоследовательность
• Проблема коммивояжера