Сегодня решим сложную задачу на динамическое программирование про поиск уникальных подпоследовательностей. Читаем условие:
Сложность задачи складывается из нескольких пунктов:
- ищутся подпоследовательности, а не подстроки,
- ищутся уникальные последовательности.
Напомню, что подстрока - это непрерывная последовательность символов с i-го до j-го. Или, на языке Python - это слайс s[i:j]. А подпоследовательность - это любая последовательность, которая может быть получена из исходной вычёркиванием произвольного числа символов. Количество подстрок O(N^2), а количество подпоследовательностей O(2^N), поэтому перебрать все не получится.
Уникальность последовательностей заставляет как-то учитывать уже посчитанные. Например из последовательности "()()" можно получить "()" тремя разными способами, но в ответ засчитывается только один. А из первого пункта получается, что подпоследовательностей очень много, поэтому запомнить учтённые не получится. Значит надо сразу считать без повторений.
Для динамического программирования на скобочные последовательности состоянием чаще всего выбирают пару: длина префикса и глубина вложенности скобок. Эта задача - не исключение.
Разберём пример из условия задачи и построим таблицу с количеством подпоследовательностей для каждого возможного состояния:
Самый левый столбец здесь отвечает за пустой префикс, так как из условия задачи следует, что пустая строка тоже является правильной скобочной последовательностью.
С первой открывающей скобкой всё тривиально и просто. А для второй скобки мы не ставим единичку на глубине 1, так как из префикса "((" строку "(" мы получили предыдущим префиксом, и она там уже учтена. Тогда остаётся только строка глубины 2. Аналогичные рассуждения с третьей скобкой.
Четвёртая скобка (первая закрывающая) может продолжить любую последовательность из "(", "((" и "(((", получив "()", "(()" и "((()" соответственно. А пятая скобка тогда может продолжить их (кроме первой): "(())" и "((())".
На этом месте остановимся и попробуем обобщить решение. Когда мы смотрели третью скобку, мы учитывали лишь продолжение от второй. А при рассмотрении четвёртой - всё с самого начала. Но для пятой - снова только четвёртую.
Дело здесь в типе скобок. Учитывать последовательности надо только за часть префикса до ближайшей скобки того же типа. Предположим, есть строка "...())))(". Если для последней скобки считать подпоследовательности вида "...(", то все они уже были посчитаны для предыдущей открывающей скобки.
Отсюда получаем переходы в динамике - суммировать все столбцы, двигаясь назад, пока не встретим скобку такого же вида. Это решение будет за O(N^3), что укладывается по время. Но и его можно ускорить - просто накапливать сумму по столбцам для обоих видов скобок.
Вот так это будет выглядеть:
Теперь уже можно писать решение. Будем использовать Python, потому что, как уже говорил, подстрок может быть очень много, поэтому понадобятся длинные числа.
Считаем входную строку и проинициализируем данные для динамики:
Здесь k - это максимальная глубина вложенности скобок. На самом деле, входная последовательность может состоять только из открывающих скобок, тогда глубина будет доходить до len(s), но из таких строк нельзя получить правильные скобочные последовательности. Поэтому половины будет достаточно.
Основное решение, как это обычно бывает в динамическом программирование, очень простое:
Для подсчёта ответа надо просуммировать первую строку таблицы:
Здесь пустую подстроку мы прибавляем отдельно, потому что не храним лишний столбец в массиве dp.
Таким образом получили квадратичное решение и посмотрели на ещё один примечательный вариант переходов между состояниями динамики.
Предыдущий выпуск: Задача 537. Перестановки - 3
Задонатить автору на бусти.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.