Динамическое программирование также используется в задачах оптимизации. Как и метод «разделяй и властвуй», динамическое программирование решает проблемы путем объединения решений подзадач. Более того, алгоритм динамического программирования решает каждую подзадачу только один раз, а затем сохраняет свой ответ в таблице, тем самым избегая повторного вычисления ответа каждый раз.
Два основных свойства проблемы предполагают, что данная проблема может быть решена с помощью динамического программирования. Эти свойства являются перекрывающимися подзадачами и оптимальной подструктурой .
Перекрывающиеся подзадачи
Подобно подходу «разделяй и властвуй», динамическое программирование также сочетает в себе решения подзадач. Он в основном используется там, где решение одной подзадачи необходимо повторно. Вычисленные решения хранятся в таблице, поэтому их не нужно пересчитывать. Следовательно, этот метод необходим там, где существует перекрывающаяся подзадача.
Например, бинарный поиск не имеет перекрывающейся подзадачи. В то время как рекурсивная программа чисел Фибоначчи имеет много перекрывающихся подзадач.
Оптимальная подструктура
Данная задача имеет свойство оптимальной подструктуры, если оптимальное решение данной задачи может быть получено с использованием оптимальных решений ее подзадач.
Например, задача Кратчайшего пути имеет следующее оптимальное свойство подструктуры —
Если узел x лежит в кратчайшем пути от исходного узла u к узлу назначения v , то кратчайший путь от u до v является комбинацией кратчайшего пути от u до x и кратчайшего пути от x до v .
Стандартные алгоритмы All Pair Shortest Path, такие как Floyd-Warshall и Bellman-Ford, являются типичными примерами динамического программирования.
Шаги подхода динамического программирования
Алгоритм динамического программирования разработан с использованием следующих четырех шагов —