线性动态规划：最长有效括号匹配子序列的变种——统计所有有效括号子序列的数量 题目描述 给定一个仅由字符 '(' 和 ')' 组成的字符串 s ，要求统计其中所有 有效括号子序列 的数量。注意，子序列不要求连续，但必须保持原字符串中的相对顺序。有效括号子序列需满足： 每个左括号 '(' 都有对应的右括号 ')' 匹配； 匹配的括号对顺序正确（即左括号在右括号之前）。 例如，字符串 "()()" 的有效括号子序列包括 "" （空序列）、 "()" 、 "()" （第二个括号对）、 "()()" 等，但需避免重复计数。 解题思路 本题是经典最长有效括号问题的扩展，但关注点从最长有效子串或子序列转为 计数所有有效子序列 。需设计动态规划状态，记录以每个字符结尾时，所有可能的有效括号子序列的数量。核心在于利用括号匹配的平衡性，通过状态转移累计合法组合数。 详细步骤 定义状态 设 dp[i][j] 表示考虑字符串 s 的前 i 个字符（下标从0开始）时， 平衡度为 j 的有效括号子序列的数量。其中平衡度 j 表示当前未匹配的左括号数量（ j ≥ 0 ）。 当 j = 0 时，表示所有左括号均被匹配，此时子序列为有效括号序列。 初始状态： dp[0][0] = 1 （空序列平衡度为0，视为有效）。 状态转移 遍历每个字符 s[i] （第 i+1 个字符），根据其是左括号或右括号进行转移： 若 s[i] == '(' ： 选择不取该字符： dp[i+1][j] += dp[i][j] ； 选择取该字符：新增一个未匹配的左括号，因此平衡度 j 增加1，即 dp[i+1][j+1] += dp[i][j] 。 若 s[i] == ')' ： 选择不取该字符： dp[i+1][j] += dp[i][j] ； 选择取该字符：需满足 j > 0 （有未匹配的左括号），此时匹配一个左括号，平衡度 j 减1，即 dp[i+1][j-1] += dp[i][j] 。 初始化与遍历顺序 初始化： dp[0][0] = 1 ，其余为0。 遍历 i 从0到 n-1 （ n 为字符串长度）， j 从0到 n （平衡度最大不超过 n ）。 最终答案： dp[n][0] ，即所有字符处理完后平衡度为0的有效子序列数量（注意包含空序列）。 复杂度分析 时间复杂度：O(n²)，需遍历所有状态。 空间复杂度：O(n²)，可优化至 O(n) 通过滚动数组。 示例验证 以 s = "()" 为例： 初始： dp[0][0] = 1 。 i=0 （字符 '(' ）： 不取： dp[1][0] += 1 → dp[1][0] = 1 ； 取： dp[1][1] += 1 → dp[1][1] = 1 。 i=1 （字符 ')' ）： 不取： dp[2][0] += dp[1][0] = 1 ； dp[2][1] += dp[1][1] = 1 ； 取：对 j=1 平衡度减1： dp[2][0] += dp[1][1] = 1 ；对 j=0 无法取右括号。 最终 dp[2][0] = 1 + 1 = 2 ，即有效子序列为 "" 和 "()" ，符合预期。 总结 通过平衡度作为状态维度，动态规划高效统计了所有有效括号子序列的数量。关键点在于理解括号匹配的平衡性，并正确设计包含“选择取/不取”的转移方程。