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

题目描述
给定一个只包含 '(' 和 ')' 的字符串 s，要求统计其中所有有效括号子串的数量。注意，这里的子串必须是连续的。有效括号字符串需满足：

1. 左括号数量等于右括号数量；
2. 从左到右遍历时，左括号的数量始终不小于右括号的数量。

例如，字符串 "()()" 的有效括号子串包括 "()"、"()" 和 "()()"，总数为 3。而 "(()" 的有效括号子串只有 "()"，数量为 1。

解题思路
本题是经典问题“最长有效括号子串”的扩展，但目标从求最长长度变为统计所有子串数量。我们可以通过动态规划记录以每个位置结尾的有效括号子串数量，并利用括号匹配的性质进行递推。

步骤详解

1. 定义状态
   设 dp[i] 表示以字符 s[i-1] 结尾的有效括号子串的数量（为方便索引处理，令 dp 数组长度比字符串长度多 1，dp[0] 表示空字符串的情况）。
   例如，若 s = "()()"，则 dp[4] 表示以最后一个字符 ')' 结尾的所有有效括号子串的数量。

2. 状态转移

   • 情况1：当前字符为 '('
     以 '(' 结尾的子串不可能是有效括号子串（因为未闭合），因此直接设 dp[i] = 0。
   • 情况2：当前字符为 ')'
     需要向前寻找与当前 ')' 匹配的 '('。具体步骤：
     a. 设当前字符索引为 i-1（因为 dp 索引偏移了 1），向前跳过以 i-2 结尾的有效子串长度（即 dp[i-1]），找到可能匹配的左括号位置 j = i - 2 - dp[i-1]。
     b. 若 j >= 0 且 s[j] == '('，说明当前 ')' 与位置 j 的 '(' 匹配成功。此时以 i-1 结尾的有效子串数量至少为 1（即刚匹配的这对括号），再加上如果 j-1 位置之前也存在有效子串，则可以拼接（例如 "()(())" 中，最后两个字符 "))" 匹配后，还能与前面的 "()" 连接）。因此：

     dp[i] = 1 + dp[j]  # dp[j] 是以 j-1 结尾的有效子串数量
     

     但需注意：这里 dp[i] 实际表示以 i-1 结尾的新增有效子串数量（即本次匹配产生的新子串），而总数量需要累加。

3. 统计总数
   遍历过程中，累加所有 dp[i] 即可得到全部有效括号子串的数量。

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

• dp[0] = 0（空字符串无有效子串）
• i=1：字符 '('，dp[1]=0
• i=2：字符 ')'，向前跳 dp[1]=0 到位置 j=0，s[0]='(' 匹配成功，dp[2] = 1 + dp[0] = 1，总数累加 1
• i=3：字符 '('，dp[3]=0
• i=4：字符 ')'，向前跳 dp[3]=0 到位置 j=2，s[2]='(' 匹配成功，dp[4] = 1 + dp[2] = 2，总数累加 2
  最终总数 = 1 + 2 = 3。

算法实现

def count_valid_parentheses_substrings(s: str) -> int:
    n = len(s)
    dp = [0] * (n + 1)  # dp[i] 表示以 s[i-1] 结尾的有效子串数量
    total_count = 0
    
    for i in range(1, n + 1):
        if s[i-1] == ')':
            j = i - 2 - dp[i-1]  # 跳过内部已匹配的子串
            if j >= 0 and s[j] == '(':
                dp[i] = 1 + dp[j]  # 当前匹配的括号对 + 前面的连续有效子串
                total_count += dp[i]
        # 若是 '(' 则 dp[i] 保持 0
    return total_count

复杂度分析

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