线性动态规划：最长有效括号匹配子串的变种——统计所有有效括号子串的数量 题目描述 给定一个仅由 '(' 和 ')' 组成的字符串 s，要求统计其中有效括号子串的数量。有效括号子串需满足： 左括号 '(' 和右括号 ')' 数量相等； 从左到右遍历时，左括号数量始终不小于右括号数量（即不会出现未匹配的右括号）。 注意：子串必须是原字符串中连续的一段。 示例 输入：s = "(()())" 输出：4 解释：有效子串为 "()", "()", "(())", "()()", "(()())"（注意重叠和嵌套情况需全面统计）。 解题过程 步骤1：理解问题核心 本题是经典"最长有效括号"问题的扩展，不再只求最长长度，而是统计所有有效子串的数量。关键点在于： 有效子串需满足括号匹配规则； 子串必须连续，且可能嵌套或相邻（如"()()"包含两个独立子串"()"和"()"）。 步骤2：定义动态规划状态 设 dp[i] 表示以字符 s[i] 结尾的最长有效括号子串的长度。但本题需要统计数量，因此需调整状态定义： 方案1：仍用 dp[i] 记录以 s[i] 结尾的最长有效括号子串长度，然后通过长度推导出所有以 i 结尾的有效子串数量。 方案2（更直接）：定义 count[i] 表示以 s[i] 结尾的有效括号子串的数量。 我们选择方案2，因为可直接累加数量。 步骤3：状态转移方程推导 遍历字符串的每个位置 i （0-indexed）： 若 s[i] == '(' ，则无法形成以 '(' 结尾的有效子串，故 count[i] = 0 。 若 s[i] == ')' ，需检查前一个字符： 情况1 ： s[i-1] == '(' ，即形如 "......()"： 此时 "()" 本身是一个有效子串。此外，若 i-2 >= 0 ，则可能还有更早的有效子串与当前 "()" 相邻（如"()()"）。但注意：我们统计的是以 i 结尾的所有有效子串，因此需加上以 i-2 结尾的有效子串数量（如果存在）。 故： count[i] = 1 + (count[i-2] if i-2 >= 0 else 0) 。 情况2 ： s[i-1] == ')' ，即形如 "......))"： 此时需检查与当前 ')' 匹配的左括号位置。设以 s[i-1] 结尾的最长有效子串长度为 L （可通过 dp[i-1] 获取），则与当前 ')' 匹配的左括号位置应为 j = i - L - 1 。 若 j >= 0 且 s[j] == '(' ，则当前 s[j...i] 是一个有效子串。此外，还可能存在以 j-1 结尾的有效子串与当前子串相邻（如"()(())"中，最后一个 ')' 匹配后，前面还有独立的"()"）。 故： count[i] = 1 + (count[j-1] if j-1 >= 0 else 0) 。 注意：若 j < 0 或 s[j] != '(' ，则 count[i] = 0 。 步骤4：初始化与遍历顺序 初始化： count[0] = 0 （单个字符无法形成有效括号对）。 遍历顺序：从左到右（i 从 1 到 n-1）。 步骤5：示例演算 以 s = "(()())" 为例（n=6）： i=0: '(' → count[ 0 ]=0 i=1: '(' → count[ 1 ]=0 i=2: ')' 且 s[ 1]='(' → 情况1：count[ 2] = 1 + count[ 0 ] = 1+0=1（子串"(0~2): ()"） i=3: '(' → count[ 3 ]=0 i=4: ')' 且 s[ 3]='(' → 情况1：count[ 4] = 1 + count[ 2 ] = 1+1=2（子串"(3~4): ()" 和 "(2~4): ()( )"？注意：实际是"(0~2)()"和"(3~4)()"，但需验证连续性） 修正：以 i=4 结尾的有效子串有： s[3..4] = "()" 连接前面的有效子串 s[0..2] = "()" 形成 "()()" （即子串 s[0..4] ） 因此确实为2个。 i=5: ')' 且 s[ 4 ]=')' → 情况2： 先求 L = dp[ 4 ] = 2（以 i=4 结尾的最长有效子串长度） j = 5 - 2 - 1 = 2，检查 s[ 2 ]=')'？不对！这里应直接计算： 实际匹配：s[ 5]的匹配位置 j = 5 - (dp[ 4] + 1) = 5 - (2 + 1) = 2，但 s[ 2 ]=')'，不匹配？ 重新检查字符串：s = "(()())"，索引：0:'(', 1:'(', 2:')', 3:'(', 4:')', 5:')' 正确计算： i=5, s[ 4]=')'，dp[ 4] 表示以索引4结尾的最长有效子串长度。以4结尾的有效子串为"()"（长度2），但实际最长应为 s[ 3..4 ]="()"？ 我们需同步计算 dp[ i ]（最长长度）以辅助： i=2: dp[ 2 ]=2（"()"） i=4: dp[ 4 ]=2（"()"） i=5: j = 5 - dp[ 4] - 1 = 5 - 2 - 1 = 2，s[ 2]=')'，但应与左括号匹配，故检查 s[ 1 ]？ 发现错误：应匹配的位置是 j = i - dp[ i-1] - 1 = 5 - dp[ 4] - 1 = 5 - 2 - 1 = 2，但 s[ 2]=')'，不匹配，所以 count[ 5 ]=0？ 但显然 s[ 0..5 ]="(()())" 是有效的。 问题出在 dp[ 4] 应为4（因为 s[ 1..4]="()()" 无效？实际 s[ 1..4]="()()" 有效，但长度4？索引1到4是"()()"？不对，s[ 1]='(', s[ 2]=')', s[ 3]='(', s[ 4 ]=')' → "()()" 有效，长度4。 所以 dp[ 4]=4？但之前算成2了。我们需要正确定义 dp[ i ]：以 i 结尾的最长有效括号子串长度。 对于 i=4： 情况1：s[ 3]='(', s[ 4 ]=')'，则基础长度=2。 再看前面：i=2 是有效结尾，dp[ 2]=2，所以连接起来：s[ 1..4]="()()" 有效，长度= dp[ 2 ] + 2 = 2+2=4。 所以 dp[ 4 ]=4。 现在 i=5：j = 5 - dp[ 4] - 1 = 5 - 4 - 1 = 0，s[ 0 ]='('，匹配成功。 则 count[ 5] = 1 + count[ -1 ]（j-1=-1，取0） = 1。 但这样漏了子串？以 i=5 结尾的有效子串还有更短的，如 s[ 3..5]="()"？不对，s[ 3..5 ]="())" 无效。 实际上，以 i=5 结尾的有效子串只有整个串 "(()())"。 但题目要求统计所有有效子串，包括中间部分。我们需重新审视：count[ i ] 应表示以 i 结尾的所有有效括号子串的数量（不同长度都算）。 对于 i=5： 最长有效子串 s[ 0..5 ]：算1个。 内部可能还有 shorter 有效子串以 i=5 结尾吗？例如 s[ 2..5]="()())" 无效；s[ 4..5 ]="))" 无效。所以只有1个。 但总数量= count[ 0] 到 count[ 5 ] 求和 = 0+0+1+0+2+1=4，与示例输出4一致。 步骤6：算法实现 需同步计算 dp[ i]（长度）和 count[ i]（数量），最后求和所有 count[ i ] 即为答案。 步骤7：复杂度分析 时间复杂度：O(n)，一次遍历。 空间复杂度：O(n)，用于存储 dp 和 count 数组。 关键点 利用历史信息（dp[ i-1 ]）找到匹配的左括号位置。 统计数量时，需考虑与前面相邻的有效子串拼接形成的更长子串。