На собеседовании по программированию динамическое программирование может быть сложной задачей. Даже начать работу над решением может быть очень непросто. В этой статье подробно объясняются 3 необходимых шага для решения задачи динамического программирования.

Динамическое программирование - это оптимизация простого рекурсивного решения проблемы. Полезно уменьшить количество выполняемых рекурсивных вызовов. Идея состоит в том, чтобы идентифицировать повторяющиеся подзадачи и сохранять результаты подзадач. Это сократит время и память, необходимые для повторного вычисления подзадач. Например, чтобы найти 5-е число Фибоначчи, нам нужно сложить 4-е и 3-е числа Фибоначчи. Все звучит хорошо, но чтобы найти 4-е число Фибоначчи, нам нужно сложить 3-е и 2-е числа Фибоначчи. Ты видишь проблему? Мы дважды вычисляем 3-е число Фибоначчи. Именно эту проблему можно решить с помощью динамического программирования.

Пример проблемы

Чтобы объяснить динамическое программирование, я буду решать проблему чисел Фибоначчи.

Числа Фибоначчи - это последовательность, называемая последовательностью Фибоначчи, в которой каждое число представляет собой сумму двух предыдущих, начиная с 0 и 1.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Например, 8-е число Фибоначчи - 21.

решение и полное понимание проблемы динамического программирования - это трехэтапный процесс

  1. Определите базовый вариант
  2. Реализовать рекурсивное решение методом грубой силы
  3. Оптимизировать с помощью динамического программирования

При желании некоторые проблемы динамического программирования можно решить с помощью жадного метода.

Определите базовый вариант

Первый шаг - определить базовый вариант. Базовый случай помогает остановить рекурсивную цепочку. В последовательности Фибоначчи, если n равно 1, мы возвращаем 1, а если n равно нулю, мы возвращаем 0. Это наш базовый случай. Когда n меньше 2, мы больше не продолжаем, а возвращаем значение.

if(n == 1) {
  return 1;
}
if(n == 0) {
  return 0;
}

Реализация рекурсивного решения методом грубой силы

Все решения начинаются с рекурсивного подхода грубой силы и оптимизируются за счет удаления ненужных вычислений. То же самое и с рядом Фибоначчи. Рекурсивные функции - это те функции, которые, по сути, вызывают сами себя.

Чтобы реализовать решение методом грубой силы, мы вычисляем значение Фибоначчи n -1 и n - 2 и складываем эти 2. Это приведет к большому количеству рекурсивных вызовов. На каждом узле мы делаем 2 рекурсивных вызова.

Анализ временной и пространственной сложности

Мы начинаем вычисление с верхнего узла и идем вниз по дереву, пока не дойдем до базового случая. Из рекурсивного дерева мы можем заметить, что на каждом уровне количество узлов равно удвоенному количеству узлов на предыдущем уровне. В корне есть только 1 узел, но на 1-м уровне есть 2 узла, затем 4,8,16 и так далее.

Для fib of 10 временные сложности будут 2¹⁰, так как нам нужно пройти на 10 уровней, и на каждом уровне количество узлов удваивается из-за логики ветвления.

Из этого шаблона мы можем сделать вывод, что временная сложность равна O (2ⁿ)

Сложность пространства равна O (n), поскольку для рекурсий требуется не более O (n) места в стеке.

Оптимизация с помощью динамического программирования

Оптимизация рекурсивной задачи методом грубой силы начинается с определения повторяющихся подзадач. Из приведенного выше рекурсивного графика мы можем заметить, что 4-е, 3-е, 2-е числа Фибоначчи вычисляются более одного раза. Если мы сохраним результат этих вычислений, мы сможем избежать нахождения значения более одного раза.

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

Использование массива для хранения уже вычисленных значений снижает количество выполняемых рекурсивных вызовов. Это снижает временную сложность с экспоненциальной до линейной.

Анализ временной и пространственной сложности

Количество выполненных рекурсивных вызовов сокращается до 2 x n, что снижает временную сложность до O (2n), за счет исключения константы временная сложность составляет O (n)

Сложность пространства по-прежнему O (n), потому что пространство стека, необходимое в любой заданной точке, равно O (n)

Практические задачи:

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

  1. Https://leetcode.com/problems/jump-game/
  2. Https://leetcode.com/problems/house-robber/
  3. Https://leetcode.com/problems/combination-sum-iv/
  4. Https://leetcode.com/problems/shortest-common-supersequence/
  5. Https://leetcode.com/problems/longest-common-subsequence/
  6. Https://leetcode.com/problems/longest-palindromic-subsequence/

Заключение

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

Практика ведет к совершенству. После долгой практики наша работа станет естественной, умелой, быстрой и устойчивой. - Брюс Ли