线性动态规划：最长有效括号匹配子串的变种—

线性动态规划：最长有效括号匹配子串的变种——统计所有有效括号子串的数量

字数 2402 2025-10-27 19:14:05

线性动态规划：最长有效括号匹配子串的变种——统计所有有效括号子串的数量

题目描述
给定一个只包含 '(' 和 ')' 的字符串 s，要求统计其中有效括号子串的数量。有效括号子串需满足：

每个左括号 '(' 都有对应的右括号 ')' 匹配；
括号匹配顺序正确（即不会出现 ")(" 这样的无效匹配）。
注意：子串需连续，且多个有效子串可能重叠或相邻。例如，"()()" 包含两个有效子串 "()" 和 "()"，而 "(())" 包含一个有效子串 "(())"（但内部 "()" 也被视为整体的一部分）。

解题思路

问题分析：与“最长有效括号子串”不同，本题要求统计所有有效子串的数量，而非最长长度。例如，"()(())" 的有效子串为 "()"、"(())" 和 "()(())" 中的 "()" 和 "(())"（注意："()(())" 本身不是连续有效括号，但内部包含两个独立子串）。
关键观察：有效子串需以右括号 ')' 结尾，且其长度取决于匹配的左括号位置。
动态规划定义：设 dp[i] 表示以字符 s[i] 结尾的有效括号子串的长度。若 s[i] 是左括号，则 dp[i] = 0（因为有效子串不能以左括号结尾）。
状态转移：
- 若 s[i] = ')' 且 s[i-1] = '('，形如 "...()"，则 dp[i] = dp[i-2] + 2（即加上前面可能存在的连续有效子串）。
- 若 s[i] = ')' 且 s[i-1] = ')'，形如 "...))"，则需检查 s[i - dp[i-1] - 1] 是否为 '('。若是，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（即当前匹配的括号对加上内部嵌套的有效子串和前面相邻的有效子串）。
统计数量：遍历过程中，若 dp[i] > 0，说明以 s[i] 结尾有一个长度为 dp[i] 的有效子串。但需注意：每个有效子串应被独立计数，例如 "()(())" 中，以索引 1 结尾的 "()" 和以索引 5 结尾的 "(())" 是两个独立子串。

循序渐进讲解
步骤 1：基础情况处理

空字符串或单字符字符串直接返回 0（无有效括号）。
初始化 dp 数组长度为 n（字符串长度），所有元素为 0。

步骤 2：遍历字符串
从索引 i = 1 开始遍历（因为 i=0 是左括号时无效）：

情况 1：s[i] = ')' 且 s[i-1] = '('
示例："....()"，此时 dp[i] = 2（当前匹配的括号对）。若 i >= 2，还需加上 dp[i-2]（前面可能存在的有效子串长度），但注意这里统计的是数量而非长度，因此先记录长度以便后续判断。

步骤 3：处理嵌套括号

情况 2：s[i] = ')' 且 s[i-1] = ')'
示例："....))"，设 prev_len = dp[i-1]（即以 s[i-1] 结尾的有效子串长度），则检查 s[i - prev_len - 1] 是否为 '('：
- 若是，说明当前 ')' 与索引 i - prev_len - 1 的左括号匹配，形成如 "(...)" 的结构。此时：
  dp[i] = prev_len + 2 + (i - prev_len - 2 >= 0 ? dp[i - prev_len - 2] : 0)
  其中 prev_len + 2 是当前匹配的括号对长度，加上前面相邻的有效子串长度。

步骤 4：统计有效子串数量

遍历 dp 数组，若 dp[i] > 0，则说明以 s[i] 结尾有一个有效子串。但需注意：每个有效子串对应其最右端索引，因此直接计数即可。例如 "()(())" 的 dp 为 [0,2,0,0,2,6]，有效子串数量为 3（索引 1、4、5 对应的子串），但实际应独立计数为 2（"()" 和 "(())"），因为索引 5 的子串包含索引 4 的子串。
修正方法：仅当 dp[i] > 0 且 i - dp[i] + 1 到 i 是一个完整有效子串时计数。但更简单的方法是：每当 dp[i] 更新时，若新增长度大于 0，则计数加 1。但需避免重复计数嵌套子串。
实际简化：直接统计所有 dp[i] > 0 的索引，但每个独立子串只计一次。正确做法是计算所有连续有效子串的段数，例如 dp 数组中连续非零段代表一个独立子串。但本题更常见的解法是：若 dp[i] 表示以 i 结尾的有效子串长度，则每当 dp[i] 非零时，计数加 1（因为每个右端点对应一个子串）。

示例演示
以 s = "()(())" 为例：

i=1：s[1]=')', s[0]='(' → dp[1] = 2，计数 +1（子串 "()"）。
i=5：s[5]=')', s[4]=')'，prev_len = dp[4]=2，检查 s[2]='(' → dp[5] = 2 + 2 + dp[1] = 6，计数 +1（子串 "(())"）。
总计数为 2。

复杂度分析

时间复杂度：O(n)，遍历一次字符串。
空间复杂度：O(n)，用于存储 dp 数组。

总结
本题通过动态规划记录以每个位置结尾的有效括号子串长度，并在遍历过程中独立计数每个有效子串。关键点在于区分相邻子串和嵌套子串，确保每个子串被正确统计一次。

线性动态规划：最长有效括号匹配子串的变种——统计所有有效括号子串的数量题目描述给定一个只包含 '(' 和 ')' 的字符串 s ，要求统计其中有效括号子串的数量。有效括号子串需满足：每个左括号 '(' 都有对应的右括号 ')' 匹配；括号匹配顺序正确（即不会出现 ")(" 这样的无效匹配）。注意：子串需连续，且多个有效子串可能重叠或相邻。例如， "()()" 包含两个有效子串 "()" 和 "()" ，而 "(())" 包含一个有效子串 "(())" （但内部 "()" 也被视为整体的一部分）。解题思路问题分析：与“最长有效括号子串”不同，本题要求统计所有有效子串的数量，而非最长长度。例如， "()(())" 的有效子串为 "()" 、 "(())" 和 "()(())" 中的 "()" 和 "(())" （注意： "()(())" 本身不是连续有效括号，但内部包含两个独立子串）。关键观察：有效子串需以右括号 ')' 结尾，且其长度取决于匹配的左括号位置。动态规划定义：设 dp[i] 表示以字符 s[i] 结尾的有效括号子串的长度。若 s[i] 是左括号，则 dp[i] = 0 （因为有效子串不能以左括号结尾）。状态转移：若 s[i] = ')' 且 s[i-1] = '(' ，形如 "...()" ，则 dp[i] = dp[i-2] + 2 （即加上前面可能存在的连续有效子串）。若 s[i] = ')' 且 s[i-1] = ')' ，形如 "...))" ，则需检查 s[i - dp[i-1] - 1] 是否为 '(' 。若是，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2] （即当前匹配的括号对加上内部嵌套的有效子串和前面相邻的有效子串）。统计数量：遍历过程中，若 dp[i] > 0 ，说明以 s[i] 结尾有一个长度为 dp[i] 的有效子串。但需注意：每个有效子串应被独立计数，例如 "()(())" 中，以索引 1 结尾的 "()" 和以索引 5 结尾的 "(())" 是两个独立子串。循序渐进讲解步骤 1：基础情况处理空字符串或单字符字符串直接返回 0（无有效括号）。初始化 dp 数组长度为 n （字符串长度），所有元素为 0。步骤 2：遍历字符串从索引 i = 1 开始遍历（因为 i=0 是左括号时无效）：情况 1 ： s[i] = ')' 且 s[i-1] = '(' 示例： "....()" ，此时 dp[i] = 2 （当前匹配的括号对）。若 i >= 2 ，还需加上 dp[i-2] （前面可能存在的有效子串长度），但注意这里统计的是数量而非长度，因此先记录长度以便后续判断。步骤 3：处理嵌套括号情况 2 ： s[i] = ')' 且 s[i-1] = ')' 示例： "....))" ，设 prev_len = dp[i-1] （即以 s[i-1] 结尾的有效子串长度），则检查 s[i - prev_len - 1] 是否为 '(' ：若是，说明当前 ')' 与索引 i - prev_len - 1 的左括号匹配，形成如 "(...)" 的结构。此时： dp[i] = prev_len + 2 + (i - prev_len - 2 >= 0 ? dp[i - prev_len - 2] : 0) 其中 prev_len + 2 是当前匹配的括号对长度，加上前面相邻的有效子串长度。步骤 4：统计有效子串数量遍历 dp 数组，若 dp[i] > 0 ，则说明以 s[i] 结尾有一个有效子串。但需注意：每个有效子串对应其最右端索引，因此直接计数即可。例如 "()(())" 的 dp 为 [0,2,0,0,2,6] ，有效子串数量为 3（索引 1、4、5 对应的子串），但实际应独立计数为 2（ "()" 和 "(())" ），因为索引 5 的子串包含索引 4 的子串。修正方法：仅当 dp[i] > 0 且 i - dp[i] + 1 到 i 是一个完整有效子串时计数。但更简单的方法是：每当 dp[i] 更新时，若新增长度大于 0，则计数加 1 。但需避免重复计数嵌套子串。实际简化：直接统计所有 dp[i] > 0 的索引，但每个独立子串只计一次。正确做法是计算所有连续有效子串的段数，例如 dp 数组中连续非零段代表一个独立子串。但本题更常见的解法是：若 dp[i] 表示以 i 结尾的有效子串长度，则每当 dp[i] 非零时，计数加 1 （因为每个右端点对应一个子串）。示例演示以 s = "()(())" 为例： i=1 ： s[1]=')' , s[0]='(' → dp[1] = 2 ，计数 +1（子串 "()" ）。 i=5 ： s[5]=')' , s[4]=')' ， prev_len = dp[4]=2 ，检查 s[2]='(' → dp[5] = 2 + 2 + dp[1] = 6 ，计数 +1（子串 "(())" ）。总计数为 2。复杂度分析时间复杂度：O(n)，遍历一次字符串。空间复杂度：O(n)，用于存储 dp 数组。总结本题通过动态规划记录以每个位置结尾的有效括号子串长度，并在遍历过程中独立计数每个有效子串。关键点在于区分相邻子串和嵌套子串，确保每个子串被正确统计一次。