10.1. Что такое динамическое программирование?
Динамическое программирование — это ещё один концепт, о котором вы скажете «О, да это же „Разделяй и властвуй“». Его суть в том, что у нашей задачи должны быть пересекающиеся подзадачи. Каждая подзадача решается один раз, а её решение заносится в кеш и используется для решения задач, зависимых от неё.
В отличие от «Разделяй и властвуй», динамическое программирование гарантирует выполнение подзадачи один раз за счёт мемоизации — кеширования ответов подзадач. Ещё одним из отличий динамического программирования является то, что подзадачи в нём связываются рекуррентно. То есть для решения одной подпроблемы требуется решение одной или нескольких других предыдущих подпроблем.
На самом деле, мы уже пользовались динамическим программированием в этом курсе! Попробуете вспомнить, что именно мы решали с его помощью.
Ответ
Использование кеширования при вычислении чисел Фибоначчи и было использованием динамического программирования! Действительно, гарантировалось, что каждая из подзадач будет решена один раз, а сами по себе подзадачи были связаны подобным графом:
А без использования динамического программирования граф подзадач выглядел бы вот так:
Динамическое программирование в этом случае значительно снизило сложность алгоритма.
Можно думать о динамическом программировании как о старшем брате «Разделяй и властвуй». Ведь если убрать из динамического программирования зависимость подзадач («на одном уровне рекурсии») друг от друга и мемоизацию, то мы получим «Разделяй и властвуй». В следующей статье мы узнаем, как при помощи этого «зверя» побороть задачу о рюкзаке!