最长有效括号匹配子序列的变种：统计所有有效括号子序列的数量 题目描述： 给定一个仅由字符 '(' 和 ')' 组成的字符串 s ，要求统计其中所有有效的括号子序列的数量。注意，子序列不要求连续，但必须保持原字符串中的相对顺序，并且每个有效的括号子序列必须是合法的括号序列（即左右括号正确匹配）。例如，字符串 "()" 的有效括号子序列有 "()" 和 "" （空序列），而 "())" 的有效括号子序列包括 "()" 、 "()" （取自不同位置）和 "" 。 解题思路： 问题分析 ：与连续子串不同，子序列允许跳过部分字符。我们需要统计所有非连续的子序列中满足括号匹配的数量。动态规划的状态设计需跟踪当前平衡度和处理到的字符位置。 状态定义 ：设 dp[i][j] 表示处理到字符串第 i 个字符时，当前平衡度为 j 的有效子序列数量。平衡度表示未匹配的左括号数量（ j≥0 ）。 状态转移 ： 初始化： dp[0][0] = 1 （空序列平衡度为0）。 对于每个字符 s[i] 和可能的平衡度 j ： 跳过当前字符 ：子序列数量继承自 dp[i][j] += dp[i-1][j] 。 选择当前字符 ： 若为 '(' ：加入后平衡度变为 j+1 ，即 dp[i][j+1] += dp[i-1][j] 。 若为 ')' ：仅当 j>0 时可加入，平衡度变为 j-1 ，即 dp[i][j-1] += dp[i-1][j] 。 结果提取 ：所有处理完的字符中，平衡度为0的状态（ dp[n][0] ）即为有效括号子序列总数（含空序列）。若需排除空序列，结果减1即可。 示例（ s = "())" ）： 步骤略解： 初始： dp[0][0]=1 。 处理 '(' （索引1）：跳过得 dp[1][0]=1 ，选择得 dp[1][1]=1 。 处理 ')' （索引2）：跳过继承，选择时对 j=1 平衡度降为0，对 j=0 无效。最终 dp[2][0]=2 （含空序列）。 结果：有效子序列数为2（实际为 "()" 和 "" ，但 "()" 因位置不同计为1种）。 关键点：通过平衡度确保合法性，状态转移覆盖所有子序列情况。