Найдите последовательность k-го действительного скобки [duplicate]

Пусть S= any valid sequence of parentheses from n( and n). Теперь любая действительная последовательность S может быть записана как S=X+Y, где

• X=valid prefix, т.е. если пересечение X слева направо, в любой момент времени numberof'(' >= numberof')'
• Y=valid suffix, т. е. если пересечение Y справа налево, в любой момент времени, numberof'(' <= numberof')'

Для любого S возможно множество пар X и Y .

В нашем примере: ()(())

`()(())` =`empty_string + ()(())` 
         = `( + )(())`
         = `() + (())` 
         = `()( + ())` 
         = `()(( + ))` 
         = `()(() + )`
         = `()(()) + empty_string`

Обратите внимание, что когда X=empty_string, число действительных S из n ( и n ) = число действительного суффикса Y из n ( и n )

Теперь алгоритм будет выглядеть следующим образом: мы начнем с X= empty_string и будем рекурсивно расти X до X=S. В любой момент времени у нас есть два варианта роста X: либо добавьте '(' или append ')'

. Пусть dp[a][b]= number of valid suffixes using a '(' and b ')' given X

nop=num_open_parenthesis_left ncp=num_closed_parenthesis_left

`calculate(nop,ncp)
{
  if dp[nop][ncp] is not known
  {
    i1=calculate(nop-1,ncp); // Case 1: X= X + "("
    i2=((nop<ncp)?calculate(nop,ncp-1):0);
/*Case 2: X=X+ ")" if nop>=ncp, then after exhausting 1 ')' nop>ncp, therefore there can be no valid suffix*/
    dp[nop][ncp]=i1+i2;
  }
   return dp[nop][ncp];
}`

Давайте возьмем пример, n = 3, т. е. 3 ( и 3 ) Теперь в самом начале X=empty_string, поэтому

dp[3][3] = число действительных последовательность S с использованием 3 ( и 3 ) = количество действительных суффиксов Y из 3 ( и 3 )