begoon's blog

By begoon, 11 years ago, In Russian
Подскажите начинающему: есть базовая динамика для задач про правильные скобочные последовательности (ПСП).

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).

Подскажите идею динамики тут. Если удасться подтолкнуть в нужном направлении, но без приведения непосредственно решения, будет еще лучше. 

Спасибо.
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it