线性动态规划：最长有效括号子串的动态规划解法进阶——统计所有有效括号子串的数量

1. 问题描述

给你一个只包含 '(' 和 ')' 的字符串 s，要求计算所有有效括号子串的数量。

• 有效括号子串定义为：该子串是连续的，且括号匹配正确（即每个 '(' 都能在其右侧找到对应的 ')'，且左右括号数量匹配）。
• 输出：一个整数，表示整个字符串中所有有效括号子串的总数。

示例
输入："(()())"
有效括号子串有：
"()"、"(())"、"()"、"(()())" 等。
需要计算所有满足条件的连续子串个数。

注意：此题与“最长有效括号子串”不同，不要求最长，而是要求所有有效括号子串的个数。

2. 动态规划思路推导

2.1 定义状态

设 dp[i] 表示以 s[i] 为结尾的最长有效括号子串的长度。
这是经典“最长有效括号子串”问题的状态定义，我们可以借用它来统计所有有效括号子串的数量。

但此题要求统计所有有效括号子串数量，而不仅仅是长度。
我们可以换个角度：
设 f[i] 表示以 s[i] 结尾的有效括号子串的个数。
最终答案 = 所有 f[i] 的和。

2.2 状态转移

考虑以 s[i] 结尾的子串。

情况 1：s[i] = '('
此时无法形成一个以 '(' 结尾的有效括号子串，所以：

f[i] = 0

情况 2：s[i] = ')'
此时需要看前一个字符 s[i-1]。

(2.1) 如果 s[i-1] = '('，形如 "...()"：

   i-1  i
...  (  )  ...

那么 s[i-1] 和 s[i] 匹配，它们组成一个有效的 "()"。
另外，这个 "()" 可能和前面以 s[i-2] 结尾的有效子串连接起来形成一个更大的有效子串。
因此：

f[i] = 1 + (f[i-2] 如果 i-2 >= 0 否则 0)

这里 f[i-2] 表示以 s[i-2] 结尾的有效子串数量，加上 "()" 后，每个这样的有效子串可以扩展出新的以 s[i] 结尾的有效子串。
但注意：这里计算的是以 i 结尾的有效括号子串个数，我们需要理解：

• 固定以 i 结尾，那么必须包含 s[i-1] 和 s[i] 这一对括号。
• 如果 i-2 是有效子串的末尾，那么 [i-2] 的有效子串 + "()" 也形成新的有效子串，且末尾是 i。
• 所以新的有效子串数量 = 1（只有 "()" 本身） + f[i-2]。

(2.2) 如果 s[i-1] = ')'，形如 "...))"：

   ...  ?  )  )
         j  i-1 i

设以 s[i-1] 结尾的最长有效括号子串长度为 L = dp[i-1]（dp数组是经典最长有效括号子串的长度）。
那么与 s[i] 匹配的 '(' 应该在位置 j = i - L - 1。

检查 j >= 0 且 s[j] = '('，则 s[j] 与 s[i] 匹配。
匹配后，[j, i] 成为一个有效括号子串。
这个新的有效括号子串还可以和它前面的有效括号子串拼接。

因此，新的有效括号子串数量：

• 基础 1 个：s[j...i] 本身。
• 加上以 s[j-1] 结尾的有效括号子串数量：f[j-1]（如果 j-1>=0），每个子串加上 s[j...i] 后形成新的有效子串，且末尾是 i。

所以：

f[i] = 1 + (f[j-1] 如果 j-1>=0 否则 0)

其中 j = i - dp[i-1] - 1，dp[i-1] 是以 i-1 结尾的最长有效括号子串长度。

2.3 同时维护 dp 数组

我们需要 dp[i] 来求 j。
dp[i] 的转移（经典最长有效括号子串的长度）：

• 如果 s[i]='('，dp[i]=0。
• 如果 s[i]=')'：
  • 如果 s[i-1]='('，dp[i] = 2 + (dp[i-2] 如果 i-2>=0 否则 0)。
  • 如果 s[i-1]=')'，j = i - dp[i-1] - 1，
    • 如果 j>=0 且 s[j]='('，dp[i] = dp[i-1] + 2 + (dp[j-1] 如果 j-1>=0 否则 0)。
    • 否则 dp[i] = 0。

2.4 举例推导

s = "(()())"
索引：0 1 2 3 4 5
字符：( ( ) ( ) )

初始化：dp[0]=0, f[0]=0

• i=1: '(' → dp[1]=0, f[1]=0

• i=2: ')', 前一个是 '(' →
  dp[2]=2+dp[0]=2
f[2]=1+f[0]=1 有效子串："( )"（索引1~2）

• i=3: '(' → dp[3]=0, f[3]=0

• i=4: ')', 前一个是 '(' →
  dp[4]=2+dp[2]=2+2=4（因为前面"(())"是有效的）
  这里注意，最长有效括号子串长度是"(())"(0~3? 检查：i=4, s[3]='(', s[4]=')'，但i=2已匹配，这里dp[4]是4，表示0~3+4? 仔细算：
  实际上 s[4]=')', s[3]='(' 匹配，dp[4] = 2+dp[2] = 2+2=4，表示以4结尾的最长有效括号子串是"(())"（索引1~4? 不对，检查：i=4, dp[4]=4，表示子串长度4，即索引[1,4]="(())"）。
  但我们的f[4]：f[4] = 1 + f[2] = 1+1=2。以4结尾的有效括号子串有两个：

  1. "()"（索引3~4）
  2. "(())"（索引1~4）

• i=5: ')', 前一个是 ')' →
  dp[4]=4, 所以 j = 5 - dp[4] - 1 = 5-4-1=0, s[0]='(' 匹配。
  dp[5] = dp[4] + 2 + dp[-1]忽略 = 4+2=6（即整个串"( ()() )"？检查：j=0, 整个串[0,5]="(()())"长度6）
  f[5] = 1 + f[-1]忽略 = 1? 等一下，这样不对，我们遗漏了前面的有效子串扩展。

  这里要注意，j=0，所以 j-1 无效，所以f[5] 新子串是 s[0..5] 这一个。
  但还有吗？以i=5结尾的有效括号子串：

  1. 整个串 "(()())"
     另外，s[4] 是 ')'，dp[4]=4，s[0]与s[5]匹配后，[0,5]是有效，但中间可能包含更小的以5结尾的子串吗？
     检查："()"（索引4~5）不是，因为中间不连续匹配？索引4~5是")"? 不对，s[4]=')', s[5]=')'，不匹配，所以不是。
     所以以5结尾的有效子串只有整个串这一个？

  但明显还有"()"(索引2~3)不是以5结尾，"(())"(1~4)也不是以5结尾。
  所以f[5]=1。

这样，最后 sum(f)=f[0]+f[1]+f[2]+f[3]+f[4]+f[5]=0+0+1+0+2+1=4。

验证：字符串 "(()())" 的有效括号子串有：
"()"(1~2), "(())"(1~4), "()"(3~4), "(()())"(0~5) 共4个。正确。

3. 算法步骤总结

1. 初始化 dp 数组长度为 n，值全 0。
2. 初始化 f 数组长度为 n，值全 0。
3. 从 i=1 遍历到 n-1：
   • 如果 s[i]='('，dp[i]=0, f[i]=0。
   • 如果 s[i]=')'：
     • 如果 s[i-1]='('：

       dp[i] = 2 + (dp[i-2] if i-2>=0 else 0)
       f[i] = 1 + (f[i-2] if i-2>=0 else 0)
       

     • 否则（s[i-1]=')'）：
       令 j = i - dp[i-1] - 1
       如果 j>=0 且 s[j]='('：

       dp[i] = dp[i-1] + 2 + (dp[j-1] if j-1>=0 else 0)
       f[i] = 1 + (f[j-1] if j-1>=0 else 0)
       

       否则：

       dp[i] = 0
       f[i] = 0
       

4. 答案为 sum(f)。

时间复杂度：O(n)
空间复杂度：O(n)

4. 边界与验证

• 空字符串：答案为 0。
• 全 '(' 或全 ')'：答案为 0。
• 示例 "()(())"：有效子串有 "()"(0~1), "(())"(2~5), "()(())"(0~5) 等，用上述算法验证即可。

5. 代码框架（Python）

def count_valid_parentheses_substrings(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    dp = [0] * n
    f = [0] * n
    total = 0
    for i in range(1, n):
        if s[i] == ')':
            if s[i-1] == '(':
                dp[i] = 2 + (dp[i-2] if i-2 >= 0 else 0)
                f[i] = 1 + (f[i-2] if i-2 >= 0 else 0)
            else:  # s[i-1] == ')'
                j = i - dp[i-1] - 1
                if j >= 0 and s[j] == '(':
                    dp[i] = dp[i-1] + 2 + (dp[j-1] if j-1 >= 0 else 0)
                    f[i] = 1 + (f[j-1] if j-1 >= 0 else 0)
        total += f[i]
    return total

通过以上步骤，我们就能精确计算字符串中所有有效括号子串的数量，而不只是最长的一个。