T4：合法括号序列 键盘上有左括号(，右括号)，和退格键-，共三个键。 牛牛希望按键n次，使得输入的字符串恰好一个合法的括号序列。 每按一次左括号(，字符串末尾追加一个左括号( 每按一次右括号)，字符串末尾追加一个右括号) 每按一次退格键-，会删掉字符串的最后一个字符， 特别的，如果字符串为空，牛牛也可以按退格，但是什么都不会发生。
方案数和具体括号序列无关，只和最终括号序列长度有关。
因为就这么多剩下的，那么管他是什么字符呢？
所以问题分成两个部分。
枚举括号序列的长度2k，
1.计算出来对于每一个长度2k，合法的括号序有多少个。
2.对于长度为2k的序列，方案数有多少。
乘法原理再加法原理即可。
对于1，是一个卡特兰数。
具体证明，可以直接转化成火车出栈顺序，或者走到（i，i）方案数。
预处理组合数。递推或者直接C(2n,n)-C(2n,n-1)
对于2，设f[i][j]表示，前i次操作后，序列长度为j的方案数。
f[i][j]=f[i-1][max(0,j-1)]+2*f[i-1][j+1]
为什么删除的操作转移有一个2
因为我们的f[i][j]其实也是一个可以变化成任意一个的合法序列，所以每个位置的填法要么是),或(，唯一确定的。
THE END