Что такое динамическое программирование?
Динамическое программирование — это метод, который позволяет нам решать класс задач, которые имеют перекрывающиеся подзадачи и оптимальную подструктуру. Давайте углубимся в эти концепции.
Оптимальная основа
Задача обладает свойством оптимальной подструктуры, если ее общее оптимальное решение может быть построено из оптимальных решений ее подзадач. Для чисел Фибоначчи, как известно, fib(n) = fib(n — 1) + fib(n — 2).
Это ясно показывает, что проблема размера n была сведена к подзадачам размеров n-1 и n-2. Следовательно, числа Фибоначчи обладают свойством оптимальной подструктуры.
Перекрывающиеся подзадачи
Рекурсивный алгоритм, который должен несколько раз решать одни и те же задачи, имеет перекрывающиеся подзадачи. Давайте рассмотрим рекурсивное решение Фибоначчи и посмотрим, как работает этот алгоритм.
Итак, вот наш наивный подход к решению проблемы Фибоначчи. Мы видим, что наша функция возвращает правильное значение, но что произойдет, если мы попытаемся найти ответ для большей позиции в последовательности?
Как мы видим, использование этого решения для больших значений очень быстро становится непрактичным.
Но почему так медленно? Чтобы понять это, давайте разберем наш предыдущий пример fib(7) и представим наши рекурсивные вызовы в виде дерева.
Ух ты! Посмотрите, даже для вычисления такой маленькой позиции 7 нам пришлось вызывать нашу функцию 25 раз!
Учитывая return fib(n — 1) + fib(n — 2), мы знаем, что для каждого вызова функции она будет вызывать себя дважды, и каждый из этих вызовов также будет вызывать себя дважды, и так далее.
Это дает нам экспоненциальную временную сложностьO(2^n).
Но давайте посмотрим, что именно вычисляется в нашем дереве.
Мы можем заметить, что у нас есть много поддеревьев, которые вычисляют одно и то же значение. Для fib(7) мы вычисляем fib(3)5 раз,fib(4) 3 раз и fib(5)2 раза. Именно это и означает наличие перекрывающихся подзадач.
Мы снова и снова решаем одни и те же проблемы, и это очень неэффективно. Должен быть способ оптимизировать это.
Запоминание
Если нам приходится решать одну и ту же проблему снова и снова, мы можем кэшировать возвращаемые значения функции и просто извлекать их из нашего кеша, если мы сталкиваемся с проблемой, которую мы уже решили ранее.
Мы можем облегчить это, используя memo-объект, который будет заполнен парами ключ-значение n : fib(n) и передан в наши рекурсивные вызовы.
Единственная разница между этим решением и предыдущим решением заключается в том, что при первом вызове функции мы передаем пустой memo-объект, который заполняется возвращаемыми значениями функция и передается другим рекурсивным вызовам.
Если мы видим, что n ранее был сохранен в мемо, мы можем вернуть кэшированное значение из нашего мемо за постоянное время и избежать последующих рекурсивных вызовов на ветке.
Давайте посмотрим, как теперь выглядит наше рекурсивное дерево.
Мы видим, что мы значительно сократили количество рекурсивных вызовов. От 25 вызовов функций без мемоизации до 11 с мемоизацией.
Кроме того, даже если мы собираемся передать большее значение в качестве входных данных и использовать мемоизацию, наше рекурсивное дерево все равно будет напоминать эту линейную цепочечную структуру.
Наша стратегия запоминания значительно улучшила временную сложность решения. От экспоненциального O(2^n) до линейного O(n).
Давайте возьмем один из примеров, которые мы использовали ранее, и посмотрим, как теперь работает наша функция с реализованной мемоизацией.
До мемоизации мы вообще не могли вычислить fib(100) за разумное время, и наша консоль казалась зависшей. Но теперь мы можем вычислить его примерно за 1 секунду.
Заключение
Динамическое программирование — очень хороший способ решения задач оптимизации, который позволяет нам эффективно использовать рекурсию и избегать многократного вычисления одних и тех же задач.
Иногда бывает трудно понять DP, поэтому не стесняйтесь снова просмотреть этот блог.
Я рекомендую использовать доску для рисования ваших рекурсивных деревьев с мемоизацией и без нее, чтобы лучше понять DP.
