题意
一个长度为 \(n\) 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。要求复杂度为 \(O(n^3)\)
分析
由题意可知，我们可以这样定义括号匹配序列：
- 空序列是括号匹配序列。
- 如果 S 是括号匹配序列，那么 \((S)\) 也是括号匹配序列。
- 如果 A 是括号匹配序列，B 是括号匹配序列，那么 AB 也是括号匹配序列。
这样的定义似乎很正确，但对于我们的计数却有不利影响，原因如下述。
首先定义状态 \(dp[l][r]\) 为区间 \([l,r]\) 中括号匹配序列的数量，转移如下：
\[\left\{
\begin{matrix}
dp[l][r] += \sum_{k = l}^r dp[l][k] * dp[k + 1][r]\\
dp[l][r] += dp[l + 1][r - 1] (s[l] == '(' \&\& s[r] == ')')
\end{matrix}
\right.
\]
乍一看还挺正确的，其实不然。
比如对于这种情况：\(()()()\)。可以这样断开：\(()\_()()\)。也可以这样断开：\(()()\_()\)。然而这两种断开方式对应的括号匹配序列是一样的，因此就重算了。思考去重的方法，多少又有点无从下手，难道没有办法了吗？
思考一下刚才的dp对应的文法：
\[括号匹配序列定义1和2：S -> (S) | ()
\]
\[括号匹配序列定义3：S -> SS
\]
可见，\(S\) 存在两种对应关系，这称作文法的二义性。这就导致我们算重复了。于是，切入点就变为如何设计文法，使其没有二义性。
比如下面的这种设计：
\[S -> A|B
\]
\[定义1和定义2：A -> ()|(A)|(B)
\]
\[定义3：B -> AB|AA
\]
可见，新增了 \(A\) 和 \(B\) 两种情况，使得不存在 \(A\) 或 \(B\) 对应两种对应关系，这就消除了文法的二义性。只需要对 \(A\) \(B\) 这两种情况分别dp，最后将总和加起来即可。设 \(f[l][r]\) 为对 \(A\) 的 dp，\(g[l][r]\) 为对 \(B\) 的dp。转移如下：
\[\left\{
\begin{matrix}
f[l][r] += f[l + 1][r - 1] + g[l + 1][r - 1](s[l] == '(' \&\& s[r] == ')')\\
g[l][r] = \sum_{k = l}^r f[l][k] * (g[k + 1][r] + f[k + 1][r])
\end{matrix}
\right.
\]
最后的答案就是 \(f[1][n] + g[1][n]\)。
如此，通过对文法设计进行改变，就能极大地降低算法复杂度。类似的思路在P7914 [CSP-S 2021] 括号序列也有体现。