Набор инструментов для алгоритмов: динамическое программирование
Динамическое программирование пугает для понимания; даже более того, попасть на техническое собеседование было страшно. Этот пост поможет вам понять, что это такое, когда и как использовать.
Прежде чем вдаваться в подробности, мы должны кратко определить, что такое динамическое программирование.
Динамическое программирование - это способ оптимизации временной сложности рекурсивного алгоритма путем кэширования ранее рассчитанных результатов.
В динамическом программировании есть еще несколько нюансов, но на данный момент это достаточная основа. Самое важное правило, о котором следует помнить, заключается в том, что вы можете использовать его только в том случае, если проблемы имеют оптимальную подструктуру.
Что такое оптимальная подконструкция? Оптимальная подструктура - это общее свойство подзадач. В частности, это общее свойство, заключающееся в том, что решения более крупных подзадач строятся на основе решений более мелких подзадач. Фантастический пример этого - последовательность Фибоначчи.
Последовательность Фибоначчи определяется как число n ᵗʰ в последовательности, равное сумме n - 1 и n - 2. Таким образом, пятое число в последовательности Фибоначчи - 5.
Fibonacci Sequence for First 5 Numbers 1, 1, 2, 3, 5
Более конкретно, мы можем определить отношение рекуррентности последовательности Фибоначчи как
Рекуррентное отношение - это математическое представление нашей рекурсивной функции. Если бы мы закодировали это, у нас было бы это.
Это работает правильно? Так зачем нам пытаться это улучшить? Для начала, временная сложность рекурсивного алгоритма O (n) = 2ⁿ. Как так? Это потому, что мы пересчитываем подзадачи, которые уже решили. Для значения fibSequence(6) мы пересчитываем fibSequence(3) 3 раза. Если вы его не видите, вот дерево рекурсии, показывающее, почему.
Для значения fib(6) мы пересчитываем fib(3) 3 раза и fib(4) 2 раза. Это довольно неэффективно. Взяв страницу из книги Гейл Макдауэлл Cracking the Coding Interview, мы собираемся выполнить BUD, чтобы повысить эффективность нашего алгоритма. Что такое БАД?
B: узкие места. Определите, где мы застреваем в нашем коде.
U: ненужная работа. Определите, где мы делаем ненужную работу.
D: дублированная работа. Определите, где мы дублируем работу.
На самом деле мы не ограничиваем себя и не выполняем ненужную работу. Мы делаем много дублированной работы. Итак, как мы можем это уменьшить? Динамическое программирование!
Если вы посмотрите, как работает последовательность Фибоначчи, мы берем сумму ранее рассчитанных подзадач. Это свойство демонстрирует оптимальную подструктуру. Мы выполнили требование по динамическому программированию.
Итак, как нам это настроить? Как перевести «кэширование ранее рассчитанных результатов» в код? Мы можем создать массив для хранения решений меньших подзадач и использовать индекс массива, чтобы показать решение подзадачи размера i.
Наша временная сложность O (n)! Мы значительно улучшили временную сложность нашего ответа.
Вот и все! Концепция динамического программирования не является сложной для понимания, но ее сложно реализовать. Это связано с тем, что большая часть работы по созданию решения динамического программирования заключается в понимании подструктур проблемы. Динамическое решение требует от вас полного понимания структуры, входных и выходных данных проблемы.
Для дальнейшей практики я рекомендую вам взглянуть на задачу внесения сдачи и задачу о ранце 0–1.
