括号匹配序列计数问题

标签：匹配 定义 括号 序列 计数问题 dp matrix

题意

一个长度为 \(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] 括号序列也有体现。

标签：匹配,定义,括号,序列,计数问题,dp,matrix
From： https://www.cnblogs.com/CZ-9/p/17366186.html