UPD:2019-10-13
$Description$:
从前有个括号序列 $s$，满足 $|s| = m$。你需要统计括号序列对 $(p, q)$ 的数量。
其中 $(p, q)$ 满足 $|p| + |s| + |q| = n$，且$ p + s + q $是一个合法的括号序列。
$Solution$:
简单$dp$或卡特兰数。括号序列匹配把左右括号分别看作$+1$，$-1$就很方便了。
$dp[i][j]$定义为放了$i$个括号，前缀和为$j$的方案数，注意转移是把括号往后放，不然会算重。
$$dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]$$
实际上这个$dp$数组可以有卡特兰数求解。
卡特兰原式子：$C_{n+m}^{m}-C_{n+m}^{m-1}$($n>m$)
在这里相当于$j+2*x=n+m$，得到$n=j+x,m=x$即可
然后$O((n-m)^2)$枚举$p$串长度和留下的括号个数
原文：https://www.cnblogs.com/2018hzoicyf/p/11670164.html