Подскажите начинающему: есть базовая динамика для задач про правильные скобочные последовательности (ПСП).
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).
Подскажите идею динамики тут. Если удасться подтолкнуть в нужном направлении, но без приведения непосредственно решения, будет еще лучше.
Спасибо.
Comments (0)
