174
правки
Изменения
Нет описания правки
Научимся считать вспомогательную '''динамику''' $d[i][j]$, где $i$ — длина скобочной последовательности (она "полуправильна": всякой закрывающей скобке имеется парная открывающая, но не все открытые скобки закрыты), $j$ — баланс (т.е. разность между количеством открывающих и закрывающих скобок), $d[i][j]$ — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.
Считать эту динамику можно следующим образом. Пусть $d[i][j]$ — величина, которую мы хотим посчитать. Если $i = 0$, то ответ понятен сразу: $d[0][0] = 1$, все остальные $d[0][j] = 0$. Пусть теперь $i > 0$, тогда мысленно переберём, чему был мог быть равен последний символ этой последовательности. Если он был равен '(', то до этого символа мы находились в состоянии $(i-1,j-1)$. Если он был равен ')', то предыдущим было состояние $(i-1,j+1)$. Таким образом, получаем формулу:
$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$
Пусть сначала допустимы только скобки '''одного''' типа.
Пусть теперь разрешён не один, а '''$k$ типов''' скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение $d[i + 1][\rm ndepth]$ на величину $k^{(2n - i - 1 - \rm ndepth) / 2}$, чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только $2n - i - 1 - \rm ndepth$, поскольку $\rm ndepth$ скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).
