最长有效括号匹配子序列的变种：统计所有有效括号子序列的数量
字数 2657 2025-10-27 19:14:05

最长有效括号匹配子序列的变种：统计所有有效括号子序列的数量

题目描述
给定一个仅由字符 '(' 和 ')' 构成的字符串 s，要求计算 s 的所有子序列中，是有效括号字符串的子序列的个数。由于结果可能很大，请返回它对 10^9 + 7 取模后的结果。

有效括号字符串定义为：

  1. 空字符串 "" 是有效括号字符串。
  2. 如果字符串 A 是有效括号字符串，那么 "(A)" 也是有效括号字符串。
  3. 如果字符串 A 和 B 都是有效括号字符串，那么 AB 也是有效括号字符串。

注意：子序列不同于子串，它不要求字符连续，但需要保持原有的相对顺序。

例如：
输入：s = "()()"
输出：7
解释：所有有效括号子序列为：

  1. "" (空字符串，索引序列为 [])
  2. "()" (索引序列为 [0, 1])
  3. "()" (索引序列为 [0, 3])
  4. "()" (索引序列为 [2, 3])
  5. "()" (索引序列为 [1, 2])
  6. "()()" (索引序列为 [0,1,2,3])
  7. "(())" (索引序列为 [0,3,1,2] 或 [1,2,0,3] 等，但构成相同的有效字符串 "(())")

解题过程

这个问题是“最长有效括号匹配子序列”的一个变种，目标不再是求最长的长度，而是统计所有可能的有效括号子序列的数量。我们可以使用动态规划来解决。

1. 定义状态
我们定义 dp[i][j] 表示考虑字符串 s 的前 i 个字符（即 s[0...i-1]）时，能够形成的、平衡度为 j 的有效括号子序列的个数。

平衡度是一个关键概念：

  • 对于一个括号字符串，我们遇到 '(' 则平衡度 +1，遇到 ')' 则平衡度 -1。
  • 一个有效的括号字符串，在整个过程中平衡度必须始终非负，并且最终的平衡度恰好为 0。

在这里，j 表示当前子序列的平衡度。例如，平衡度为 0 表示左右括号完全匹配（如 "()"）；平衡度为 1 表示多一个左括号（如 "(" 或 "(()"）。

2. 状态转移方程
我们逐个考虑字符串 s 中的每个字符，并决定是否在子序列中包含它。

对于第 i 个字符（索引为 i-1），我们有两种选择：不选取它或者选取它。

  • 不选取第 i 个字符：那么状态直接从 dp[i-1][j] 继承过来。即 dp[i][j] 至少包含 dp[i-1][j]。

  • 选取第 i 个字符：这取决于第 i 个字符是 '(' 还是 ')'。

    • 如果 s[i-1] == '('：选取这个 '(' 会使得平衡度增加 1。因此，如果我们在前 i-1 个字符中形成了一个平衡度为 j-1 的子序列，那么加上这个 '(' 后，就形成了一个平衡度为 j 的子序列。所以贡献是 dp[i-1][j-1]。
    • 如果 s[i-1] == ')'：选取这个 ')' 会使得平衡度减少 1。但是，这个操作只有在平衡度减少后不会变成负数（即 j+1 >= 0）时才是有意义的，因为有效括号序列的平衡度在任意时刻都不能为负。因此，如果我们在前 i-1 个字符中形成了一个平衡度为 j+1 的子序列，那么加上这个 ')' 后，就形成了一个平衡度为 j 的子序列。所以贡献是 dp[i-1][j+1]。

综合两种情况，状态转移方程如下：
dp[i][j] = dp[i-1][j] + (选取第i个字符带来的贡献)

3. 初始状态

  • dp[0][0] = 1：考虑前 0 个字符（空字符串），可以形成一个平衡度为 0 的空子序列。
  • 对于其他的 i=0, j>0，dp[0][j] = 0。
  • 我们通常将 dp 数组的维度设置为 [n+1] x [n+1]，因为平衡度的最大可能值不会超过字符串长度 n。

4. 计算顺序与答案
我们按照 i 从 0 到 n（字符串长度）的顺序进行遍历。对于每个 i，遍历所有可能的平衡度 j（j 的范围通常从 0 到 n，但因为平衡度可能为负？实际上，在我们的状态定义和转移中，我们只关心 j >= 0 的情况，因为 j < 0 的状态对于形成有效序列没有贡献，可以忽略或初始化为 0）。

最终的答案就是 dp[n][0]，即考虑整个字符串 s 后，平衡度为 0（完全匹配）的所有有效括号子序列的数量。注意，这个数量包含了空字符串。

5. 示例推导（s = "()"）
n = 2。
初始化：dp[0][0] = 1, 其他为 0。

  • i=1，考虑第一个字符 s[0] = '('。

    • 对于 j=0：不选贡献 dp[0][0]=1；选取：字符是 '('，贡献来自 dp[0][0-1]，但 j-1=-1，我们通常不考虑负平衡度的状态（初始为0），所以贡献为0。dp[1][0] = 1 + 0 = 1。
    • 对于 j=1：不选贡献 dp[0][1]=0；选取：字符是 '('，贡献来自 dp[0][1-1]=dp[0][0]=1。dp[1][1] = 0 + 1 = 1。
    • 其他 j 类似，主要就这两个状态。
    • 当前状态：dp[1] = [1, 1, 0, ...] (表示平衡度0有1个，平衡度1有1个)。

  • i=2，考虑第二个字符 s[1] = ')'。

    • 对于 j=0：不选贡献 dp[1][0]=1；选取：字符是 ')'，贡献来自 dp[1][0+1]=dp[1][1]=1。dp[2][0] = 1 + 1 = 2。
    • 对于 j=1：不选贡献 dp[1][1]=1；选取：字符是 ')'，贡献来自 dp[1][1+1]=dp[1][2]=0。dp[2][1] = 1 + 0 = 1。
    • 当前状态：dp[2] = [2, 1, 0, ...]。

最终答案 dp[2][0] = 2。
有效子序列有："" 和 "()"。符合预期。

6. 复杂度与优化

  • 时间复杂度：O(n²)，需要遍历 n 个字符，每个字符最多考虑 n 种平衡度。
  • 空间复杂度：O(n²)，使用二维 DP 数组。可以优化到 O(n)，因为当前状态 i 只依赖于状态 i-1。

7. 总结
这个方法的核心在于使用动态规划，状态定义为“前 i 个字符形成的平衡度为 j 的子序列个数”，通过决策是否选取当前字符，并正确处理 '(' 和 ')' 对平衡度的影响，最终得到所有完全匹配（平衡度为0）的子序列数量。

最长有效括号匹配子序列的变种：统计所有有效括号子序列的数量 题目描述 给定一个仅由字符 '(' 和 ')' 构成的字符串 s，要求计算 s 的所有子序列中，是有效括号字符串的子序列的个数。由于结果可能很大，请返回它对 10^9 + 7 取模后的结果。 有效括号字符串定义为： 空字符串 "" 是有效括号字符串。 如果字符串 A 是有效括号字符串，那么 "(A)" 也是有效括号字符串。 如果字符串 A 和 B 都是有效括号字符串，那么 AB 也是有效括号字符串。 注意：子序列不同于子串，它不要求字符连续，但需要保持原有的相对顺序。 例如： 输入：s = "()()" 输出：7 解释：所有有效括号子序列为： "" (空字符串，索引序列为 [ ]) "()" (索引序列为 [ 0, 1 ]) "()" (索引序列为 [ 0, 3 ]) "()" (索引序列为 [ 2, 3 ]) "()" (索引序列为 [ 1, 2 ]) "()()" (索引序列为 [ 0,1,2,3 ]) "(())" (索引序列为 [ 0,3,1,2] 或 [ 1,2,0,3 ] 等，但构成相同的有效字符串 "(())") 解题过程 这个问题是“最长有效括号匹配子序列”的一个变种，目标不再是求最长的长度，而是统计所有可能的有效括号子序列的数量。我们可以使用动态规划来解决。 1. 定义状态 我们定义 dp[i][j] 表示考虑字符串 s 的前 i 个字符（即 s[ 0...i-1]）时，能够形成的、 平衡度 为 j 的有效括号子序列的个数。 平衡度 是一个关键概念： 对于一个括号字符串，我们遇到 '(' 则平衡度 +1，遇到 ')' 则平衡度 -1。 一个有效的括号字符串，在整个过程中平衡度必须始终非负，并且最终的平衡度恰好为 0。 在这里， j 表示当前子序列的平衡度。例如，平衡度为 0 表示左右括号完全匹配（如 "()"）；平衡度为 1 表示多一个左括号（如 "(" 或 "(()"）。 2. 状态转移方程 我们逐个考虑字符串 s 中的每个字符，并决定是否在子序列中包含它。 对于第 i 个字符（索引为 i-1），我们有两种选择： 不选取 它或者 选取 它。 不选取第 i 个字符 ：那么状态直接从 dp[i-1][j] 继承过来。即 dp[i][j] 至少包含 dp[i-1][j] 。 选取第 i 个字符 ：这取决于第 i 个字符是 '(' 还是 ')'。 如果 s[i-1] == '(' ：选取这个 '(' 会使得平衡度增加 1。因此，如果我们在前 i-1 个字符中形成了一个平衡度为 j-1 的子序列，那么加上这个 '(' 后，就形成了一个平衡度为 j 的子序列。所以贡献是 dp[i-1][j-1] 。 如果 s[i-1] == ')' ：选取这个 ')' 会使得平衡度减少 1。但是，这个操作只有在平衡度减少后不会变成负数（即 j+1 >= 0）时才是有意义的，因为有效括号序列的平衡度在任意时刻都不能为负。因此，如果我们在前 i-1 个字符中形成了一个平衡度为 j+1 的子序列，那么加上这个 ')' 后，就形成了一个平衡度为 j 的子序列。所以贡献是 dp[i-1][j+1] 。 综合两种情况，状态转移方程如下： dp[i][j] = dp[i-1][j] + (选取第i个字符带来的贡献) 3. 初始状态 dp[0][0] = 1 ：考虑前 0 个字符（空字符串），可以形成一个平衡度为 0 的空子序列。 对于其他的 i=0, j>0 ， dp[0][j] = 0 。 我们通常将 dp 数组的维度设置为 [n+1] x [n+1] ，因为平衡度的最大可能值不会超过字符串长度 n。 4. 计算顺序与答案 我们按照 i 从 0 到 n（字符串长度）的顺序进行遍历。对于每个 i，遍历所有可能的平衡度 j（j 的范围通常从 0 到 n，但因为平衡度可能为负？实际上，在我们的状态定义和转移中，我们只关心 j >= 0 的情况，因为 j < 0 的状态对于形成有效序列没有贡献，可以忽略或初始化为 0）。 最终的答案就是 dp[n][0] ，即考虑整个字符串 s 后，平衡度为 0（完全匹配）的所有有效括号子序列的数量。注意，这个数量包含了空字符串。 5. 示例推导（s = "()"） n = 2。 初始化： dp[0][0] = 1 , 其他为 0。 i=1 ，考虑第一个字符 s[ 0 ] = '('。 对于 j=0：不选贡献 dp[0][0]=1 ；选取：字符是 '('，贡献来自 dp[0][0-1] ，但 j-1=-1，我们通常不考虑负平衡度的状态（初始为0），所以贡献为0。 dp[1][0] = 1 + 0 = 1 。 对于 j=1：不选贡献 dp[0][1]=0 ；选取：字符是 '('，贡献来自 dp[0][1-1]=dp[0][0]=1 。 dp[1][1] = 0 + 1 = 1 。 其他 j 类似，主要就这两个状态。 当前状态： dp[1] = [1, 1, 0, ...] (表示平衡度0有1个，平衡度1有1个)。 i=2 ，考虑第二个字符 s[ 1 ] = ')'。 对于 j=0：不选贡献 dp[1][0]=1 ；选取：字符是 ')'，贡献来自 dp[1][0+1]=dp[1][1]=1 。 dp[2][0] = 1 + 1 = 2 。 对于 j=1：不选贡献 dp[1][1]=1 ；选取：字符是 ')'，贡献来自 dp[1][1+1]=dp[1][2]=0 。 dp[2][1] = 1 + 0 = 1 。 当前状态： dp[2] = [2, 1, 0, ...] 。 最终答案 dp[2][0] = 2 。 有效子序列有："" 和 "()"。符合预期。 6. 复杂度与优化 时间复杂度：O(n²)，需要遍历 n 个字符，每个字符最多考虑 n 种平衡度。 空间复杂度：O(n²)，使用二维 DP 数组。可以优化到 O(n)，因为当前状态 i 只依赖于状态 i-1。 7. 总结 这个方法的核心在于使用动态规划，状态定义为“前 i 个字符形成的平衡度为 j 的子序列个数”，通过决策是否选取当前字符，并正确处理 '(' 和 ')' 对平衡度的影响，最终得到所有完全匹配（平衡度为0）的子序列数量。