「BalticOI 2012 Day1」括号 题解

算法分析

这是一个动态规划问题，需要计算将给定非正规括号序列还原为正规括号序列的方案数。

关键观察

1. 问题转化：给定一个由 ( 和 ) 组成的序列，其中某些 ( 原本可能是 [，某些 ) 原本可能是 ]
2. 约束条件：
   • 序列必须包含至少一对 []
   • 整个序列必须是正规括号序列
   • 将所有的 [ 和 ] 替换为 ( 后得到输入序列

动态规划状态设计

定义 f[i][j] 表示处理到第 $i$ 个字符时，当前未匹配的左括号数量为 $j$ 的方案数。

状态转移：

• 如果当前字符是 )，它只能匹配前面的左括号：f[i][j] = f[i-1][j+1]
• 如果当前字符是 (，它可以是：
  • 新的左括号：f[i][j] += f[i-1][j-1]
  • 或者是 [ 的替换（但需要满足约束条件）

算法优化

使用滚动数组优化空间复杂度：

• 只维护当前行和前一行的状态
• 空间复杂度从 $O(n^2)$ 降为 $O(n)$

核心代码解析

f[0][0] = 1;  // 初始状态：空序列，未匹配括号数为0

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
        // 当前字符作为右括号
        f[i & 1][j] = f[(i - 1) & 1][j + 1];
        
        // 当前字符作为左括号
        if (s[i] == '(' && j) {
            f[i & 1][j] = (f[i & 1][j] + f[(i - 1) & 1][j - 1]);
            if (f[i & 1][j] >= mod)
                f[i & 1][j] -= mod;
        }
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n \leq 3 \times 10^4$
• 空间复杂度：$O(n)$，使用滚动数组优化

算法标签

主要标签：

• 动态规划 ⭐⭐⭐⭐⭐
• 括号序列 ⭐⭐⭐⭐
• 计数问题 ⭐⭐⭐⭐

技术标签：

• 滚动数组优化 ⭐⭐⭐⭐
• 状态压缩 ⭐⭐⭐
• 组合数学 ⭐⭐

问题类型：

• 序列计数 ⭐⭐⭐⭐
• 约束满足 ⭐⭐⭐

算法思路总结

1. 状态定义：f[i][j] 表示前 $i$ 个字符，未匹配左括号数为 $j$ 的方案数
2. 状态转移：
   • 遇到 )：只能作为右括号匹配
   • 遇到 (：可以作为左括号或 [ 的替换
3. 空间优化：使用滚动数组降低空间复杂度
4. 最终答案：f[n][0] 表示完整匹配的方案数

适用场景

这种动态规划方法适用于：

• 括号序列相关的计数问题
• 带有约束条件的序列生成问题
• 需要处理大量状态的计数问题

该解法通过巧妙的状态设计和滚动数组优化，在保证正确性的同时有效控制了空间复杂度，是处理大规模括号序列计数问题的经典方法。