Подскажите начинающему: есть базовая динамика для задач про правильные скобочные последовательности (ПСП).
F(n, k) = F(n-1, k-1) + F(n-1, k+1).
Многие задачи про скобки к ней сводятся. Но есть такой вариант, когда надо найти количество правильных скобочных последовательностей из n открывающихся скобок, причем максимальная глубина на всей строке (разница между открывающимися и закрывающимися скобками) должна быть равна k. Например, для n=3 и k=2 последовательность ()(()) верная (глубина 2), а ((())) нет (глубина 3).
F(n, k) - количество ПСП длиной n и разницей между количеством открывающихся и закрывающихся скобок (глубиной) k:
F(n, k) = F(n-1, k-1) + F(n-1, k+1).
Многие задачи про скобки к ней сводятся. Но есть такой вариант, когда надо найти количество правильных скобочных последовательностей из n открывающихся скобок, причем максимальная глубина на всей строке (разница между открывающимися и закрывающимися скобками) должна быть равна k. Например, для n=3 и k=2 последовательность ()(()) верная (глубина 2), а ((())) нет (глубина 3).
Подскажите идею динамики тут. Если удасться подтолкнуть в нужном направлении, но без приведения непосредственно решения, будет еще лучше.
Спасибо.
А уже f (не больше k) найти не сложнее, чем в исходной задаче без ограничений.
Будут переходы назад такие:
для k < K: f (n, k, t) = f (n - 1, k - 1, t) + f (n - 1, k + 1, t).
для k = K: f (n, K, 1) = f (n - 1, K - 1, 0) + f (n - 1, K - 1, 1),
f (n, K, 0) = 0.
Переходы строятся механически. Пусть мы в состоянии (n, k, t). Попасть в него можно не более чем четырьмя способами: отрежем последний символ (два случая) и рассмотрим флаг (x два случая). Каждый случай либо есть как слагаемое, либо нет.
Кстати, g (a, b), a <= b - количество способов построить начало из a открывающих и b закрывающих скобок - часто удобнее на практике: как минимум, тратится в два раза меньше памяти.
Параметры будут такие: n,max,k. Где n - текущая длина , которую мы уже выстроили max - максимальная из встречающихся нам глубин, что уже есть k - текущая глубина. Писать можно рекурсивно, только не забудь что у нас при некоторых даже не очень больших значениях примерно 100 , уже нужно писать длинную арифметику.