括号序列计数

标签：min ge 括号 计数 choose && 序列

1.设\(f(n,m,k)\)表示有\(n\)个左括号，\(m\)个右括号，子序列中合法括号序列最长长度为\(2k\)的括号序列，转移为

\[f(n,m,k)= \left\{ \matrix{ {n+m}\choose n && k\ge min(n,m)\\ f(n-1,m,k-1)+f(n,m-1,k) && k<min(n,m) } \right. \]

通过归纳可以得到

\[f(n,m,k)= \left\{ \matrix{ {n+m}\choose n && k\ge min(n,m)\\ {n+m}\choose k && k<min(n,m) } \right. \]

2.对于一个括号序列来说，要想构造一个最长的合法子括号序列，没有用上的右括号的数量就是前缀和的min。可以考虑像算卡特兰数那样将跨过某条斜线之后的路径全部取反。

标签：min,ge,括号,计数,choose,&&,序列
From： https://www.cnblogs.com/lprdsb/p/18004776