Существует множество вариантов задач динамического программирования. Иногда программисты сталкиваются с трудностями при проверке того, является ли данная проблема проблемой динамического программирования или нет.

Поэтому понимание этой идеи важно, потому что как только мы решим, что данную проблему можно решить с помощью динамического программирования, она выберет совершенно другой путь решения. На практике существует две популярные категории задач, которые можно решить с помощью динамического программирования: 1) задачи оптимизации и 2) задачи подсчета.

1. Проблема оптимизации

В задаче оптимизации нам нужно найти оптимальное решение (минимальное, максимальное, самое длинное, самое короткое и т. д.) в большом пространстве решений, где каждое решение имеет значение. Идея решения методом грубой силы состоит в том, чтобы изучить каждое возможное решение с помощью рекурсии и определить среди них оптимальные решения. Но, к сожалению, общее количество подзадач может оказаться больше, чем ожидалось, из-за неоднократного возникновения одной и той же подзадачи.

Пример задачи оптимизации 1: Задача о самой длинной общей подпоследовательности

Учитывая две строки массива X[] и Y[] размера m и n,, напишите код, чтобы найти длину самой длинной общей последовательности. Общая подпоследовательность двух строк — это подпоследовательность, общая для обеих строк. Если общей подпоследовательности нет, верните 0.

Может быть несколько возможных общих подпоследовательностей самой длинной длины, но нужно просто вернуть длину самой длинной общей подпоследовательности. Итак, это задача оптимизации, пространство решения которой очень велико. Если строка X имеет размер m, то возможной подпоследовательности будет 2^m — 1. Как? Идея проста!

Для каждого символа в строке будет два варианта выбора: либо он является частью подпоследовательности, либо не является частью подпоследовательности. Чтобы найти общее количество подпоследовательностей, нам нужно умножить вероятность для всех m символов, что составляет 2^m (умножить 2 m количество раз). Если игнорировать возможность пустых подпоследовательностей, общее количество подпоследовательностей = 2^m — 1. Аналогично строка Y размера n имеет 2^n — 1 подпоследовательность.

Let's understand this with an example.
Suppose X[] = "ABC" which has three characters. 
If we take 1 when character is part of the 
subsequence and take 0 not part of the subsequence. 

Then we can generate all 8 subsequences by masking 
the input string with the bits of all 3 size bianry numbers.

A B C
0 0 0 => Empty
0 0 1 => C
0 1 0 => B
0 1 1 => BC
1 0 0 => A
1 0 1 => AC
1 1 0 => AB
1 1 1 => ABC

If we have m size string then total count 
of m size bianry numbers will be 2^m.

Одна из основных идей заключалась в том, чтобы изучить все возможные подпоследовательности обеих строк, сравнить каждую подпоследовательность X с каждой подпоследовательностью Y и найти среди них общую и самую длинную. Таким образом, это решение потребует экспоненциального времени и крайне неэффективно.

Мы также можем увидеть закономерности перекрытия и повторения подзадач при разработке рекурсивного решения. Это также одна из причин того, что наше пространство решений является экспоненциальным временем. Таким образом, мы можем использовать подход DP «сверху вниз» или «снизу вверх» и оптимизировать временную сложность до времени O(mn), используя пространство O(mn). Даже мы можем сделать еще один шаг вперед и решить эту проблему в пространстве O(n).

Пример задачи оптимизации 2: Задача о максимальной сумме подмассивов

Учитывая массив A размера n, содержащий положительные и отрицательные целые числа, цель состоит в том, чтобы определить индексы i и j, 1 ‹= i ‹= j ‹= n, такие, что A[i] + A[i + 1] + … + A[j] — максимум. Другими словами, цель состоит в том, чтобы найти смежные значения массива A[i], A[i +1], . . . , A[j] такие, что их сумма A[i] + A[i + 1] + … + A[j] максимальна.

Это задача оптимизации, поскольку мы хотим оптимизировать, то есть максимизировать сумму из всего возможного пространства решений. Пространством решения для этого является набор всех пар индексов i и j, 1 ‹= i ‹= j ‹= n, причем каждая пара дает сумму. Таким образом, таких сумм n².

Обратите внимание, что все эти суммы являются кандидатами на решение задачи (оптимумом является та, которая является максимальной суммой). Это так называемые возможные решения. Возможные решения – это те, которые удовлетворяют ограничениям проблемы. Здесь ограничение состоит в том, что сумма массива должна относиться к непрерывному подмассиву, т. е. она включает в себя все значения массива между индексами i и j (включая A[i] и A[j]).

Легко видеть, что задачу можно решить, вычислив все возможные суммы массива n² и выбрав максимальную из них. Это требует как минимум n² операций; на самом деле даже больше, поскольку для вычисления конкретной суммы A[i] + · · · + A[j] требуется j − i операций сложения. Несложно подсчитать, что общее количество операций сложения по всем суммам массива O(n²) равно O(n³). Используя разделяй и властвуй, можно спроектировать O(nlog n), но используя DP, мы можем разработать простой и элегантный алгоритм за время O(n), который также легко реализовать.

Другие примеры проблем оптимизации

2. Задача подсчета

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

Задачи на подсчет Пример 1: Подсчитайте количество способов добраться до n-й лестницы

Лестница состоит из n ступенек, и за раз можно подняться либо на 1, либо на 2 ступеньки. Нам нужно посчитать и вернуть общее количество уникальных способов подняться на вершину лестницы. Порядок шагов имеет значение.

Это задача подсчета, и есть несколько способов добраться до n-й ступеньки. Если мы думаем рекурсивно, есть два способа добраться до n-й ступеньки: либо с (n-1)-й ступеньки, сделав 1 шаг, либо с (n-2)-й ступеньки, сделав 2 шага. Таким образом, общее количество способов добраться до n-й ступеньки = Общее количество способов добраться до (n-1)-й ступеньки + Общее количество способов добраться до (n-2)-й ступеньки.

Итак, рекуррентное соотношение: восхождение(n) = восхождение(n-1) + восхождение(n-2), где восхождение(1) = 1 и восхождение(2) = 2. Это похоже на рекуррентное соотношение ряда Фибоначчи, поэтому мы можем применить идею динамического программирования.

Задачи подсчета. Пример 1: Подсчет путей от верхнего левого угла до правого нижнего угла матрицы MxN

Вы задали сетку NxM и находитесь в начальной точке, то есть в 1-й строке и 1-м столбце или (0,0). Вы можете двигаться либо вниз (D), либо вправо (R). Итак, проблема состоит в том, чтобы найти общее количество путей, начиная от первой ячейки до последней ячейки, то есть (N, M).

Решение с помощью комбинаторики

Мы можем ясно наблюдать одну вещь: если нам нужно достичь формы (0,0) к (N, M), нам нужно сделать N шагов вниз, а M шагов вправо. Итак, как нам сформулировать решение и посчитать общее количество путей? Если мы внимательно посмотрим на каждую ячейку, у нас есть два варианта: двигаться вниз или вправо. Но есть одно ограничение: эти варианты выбора должны иметь N вариантов вниз и M вариантов вправо, поскольку только тогда мы сможем добраться до последней ячейки. Например, мы можем добраться до последней ячейки, если перейдём RRDRDRDDRD…….вверх к ND и M R (здесь R означает вправо, а D вниз).

Проблему можно решить простой комбинаторикой. По сути, каждый путь состоит из N движений вниз и M движений вправо. Поскольку нам нужно только N шагов, чтобы достичь дна из этих (N+M) шагов, пути отличаются друг от друга выбором N движения вниз из (N+M) возможностей. Итак, общее количество путей можно получить как количество способов выбрать N из (N+M) разных вещей, то есть как C(M+N, N) = (M + N)!/(N !)(М!).

Мы можем думать и по-другому! Мы можем достичь правого конца, используя M шагов из (N+M) шагов. Итак, общее количество путей можно получить как количество способов выбрать M из (N+M) разных вещей, то есть как C(M+N, M) = (M + N)!/(N !)(М!). В обоих случаях ответ один и тот же, т.е. (M + N)!/(N!)(M!).

Рекурсивное решение: мы можем добраться до ячейки (M, N) из ячеек (N-1, M) и (N, M-1). Таким образом, общее количество способов добраться до (M, N)-й ячейки = общее количество способов добраться до (N-1, M)-й ячейки + общее количество способов добраться до (N-1, M)-й ячейки => pathCount(N,M) = pathCount(N-1,M)+pathCount(N,M-1)

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

Другие примеры проблем со подсчетом

Критическое примечание для выявления проблемы динамического программирования

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

Но описанный выше подход может занять немного времени, поскольку нам придется пройти два важных процесса: проектирование рекурсивного решения и построение рекурсивного дерева! Критический вопрос: есть ли способ быстро выявить такие проблемы? Вот одна идея с использованием математики и комбинаторики, которая может эффективно работать в большинстве сценариев.

Когда данная проблема является проблемой оптимизации или подсчета, мы можем применить комбинаторику для подсчета всех возможных кандидатов на решение. Если пространство решений очень велико или экспоненциально, эту проблему можно решить с помощью динамического программирования. Причина проста: рекурсия должна будет исследовать все возможные кандидаты на решение, что является экспоненциальным подсчетом. Любое такое рекурсивное решение может привести к повторению сценариев подзадач.

Наслаждайтесь обучением, наслаждайтесь алгоритмами!

Дополнительную информацию можно найти в наших бесплатных курсах DSA и блогах с интервью по программированию. Если вы хотите учиться вживую, изучите эти два курса:

Если у вас есть какие-либо вопросы/сомнения/отзывы, напишите нам по адресу [email protected].