Скобочная последовательность - строка состоящая только из открывающихся и закрывающихся скобок. Для простоты будем рассматривать только круглые скобки. Правильная скобочная последовательность (ПСП) задаётся рекуррентно и для неё верны следующие утверждения:
Если существуют другие виды скобок (квадратные, фигурные), просто дополняется последний пункт.
Если может быть только один вид скобок, достаточно поддерживать одну переменную, так называемый баланс. Когда встречаем открывающую скобку - увеличиваем переменную на один, когда закрывающую - уменьшаем. В конце баланс должен быть нулевой и никогда не должен быть меньше нуля.
bool isPSP(string s) {
int balance = 0;
for(auto i : s) {
if(i == '(') balance++;
else if(i == ')') balance--;
if( balance<0 ) return false;
}
return !balance; // баланс должен быть нулевым
}
При наличии разных видов скобок теперь необходим стек. Если скобка открывающая - кладём ее в стек. В противном случае берём из стека последнюю открывающую. Если она соответствует нашей - все ок, иначе не ПСП. Если же стек оказался пустым во время попытки оттуда вытащить - также последовательность не ПСП. Кроме того, по окончании цикла стек должен быть пустым.
Пусть дана скобочная последовательность \(s\) длины \(n\). Выпишем ее префиксный баланс \(pref_i\) (то есть баланс каждого префикса - разность количества открывающих и закрывающих скобок). Тогда если \(s\) - ПСП, тогда \(pref_n = 0\), а также \( min(pref_i) \ge 0\).
Отсюда можно решать задачи проверки ПСП на отрезке - пускай надо отвечать на запросы \( (l;r) \) - является ли подстрока \( s_l,s_{l+1}...s_r\) ПСП. Проверим правда ли, что \( pref_r - pref_{l-1} = 0 \), а также что \( min(pref_i) - pref_{l-1} \ge 0 \). Задача (а также ее усложненные версии) тривиально решается структурами на отрезке.
Рассмотрим все ПСП длиной \(2n\).
Можно рассмотреть динамику \(dp[i][j] \), где \(i\) - длина скобочной последовательности, а \(j\) - баланс. Динамить будем, разумеется, количеству скобочных последовательностей. Переход будет происходить следующим образом: мы можем увеличить длину последовательности только добавляя одну из скобок. В зависимости от вида скобки баланс будет изменяться на один. Таким образом: \(dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]\). Конечно же, \( 0\le j \le n \). Таким образом, сложность \(O(n^2)\).
Достаточно легко заметить, что количество ПСП при увеличении длины возникает ряд совпадающий с числами Каталана, которые вычисляются, как через рекурентную формулу за \(O(n^2)\), так и за \(O(n)\).
При наличии разного вида скобок следует домножить полученное число на \(q^n\), где \(q\) - количество видов скобок.
Задача на использование этой динамики
Пусть необходимо найти длину самой длинной правильную скобочную подпоследовательность. Переформулируем: какое наименьшее количество символов необходимо удалить, чтобы получить ПСП. Рассмотрим динамику \(dp[l, r]\), где \(l\) и \(r\) это границы подстроки, а само значение - ответ для этой подстроки. Соответственно, \(dp[0, n-1]\) ответ на задачу. Теперь же рассмотрим все переходы. Обратимся к определению ПСП и сделаем вывод: - если какая-то строка \([l; r]\) находится внутри двух скобок "(...)", то один ответ для \(dp[l-1, r+1] = dp[l, r]\) - также конкатенация двух ПСП дает как результат тоже ПСП. Значит, для \(l < r\) переберем все \(l\le i\le r-1\), и выберем минимальное \( dp[l,i]+dp[i+1,r]\).
Перебор всевозможных \(l\) и \(r\) плюс обработка каждого подотрезка - асимптотика алгоритма \(O(n^3)\)
Дано \(n\) строк, состоящих из символов двух типов - '(' и ')' - скобочные последовательности. Необходимо определить можно ли составить из этих строк ПСП.
Сначала определим для каждой строки два параметра, которые нас действительно волнуют, а именно суммарный баланс (количество открывающих скобок минус количество закрывающих) и минимальный баланс на префиксе.
Давайте разделим наши строки на две группы: те, у которых суммарный баланс неотрицательный, и те, у которых он отрицателен. Сначала в каком-то порядке будут идти строки с положительным и нулевым суммарным балансом, а потом с отрицательным.
Интуиция здесь такая: сначала баланс у нас растет, а потом уменьшается.
Теперь рассмотрим, как же упорядочить обе группы последовательностей.
Теперь сконкатенируем сначала строки с неотрицательным балансом, а потом с отрицательным. Проверим является ли полученная строка ПСП.
Для решения задачи также существуют и другие жадники.