线性动态规划：最长有效括号子串的不同计数问题

题目描述：
给定一个只包含 '(' 和 ')' 的字符串 s，要求统计所有可能的不同有效括号子串的个数。
注意：

1. 有效括号子串需满足括号匹配规则（每个左括号都能在子串内找到对应的右括号，且顺序正确）。
2. 子串必须是原字符串的连续部分。
3. 如果两个子串的起始位置或结束位置不同，则视为不同的子串。
4. 需要统计的是所有可能的有效括号子串的数量，而不是最长的那一个。

例如：

• 输入："()()"
  输出：3
  解释：有效括号子串有 "()"（位置0-1）、"()"（位置2-3）、"()()"（位置0-3），共3个。
• 输入："(())"
  输出：2
  解释：有效括号子串有 "()"（位置1-2）、"(())"（位置0-3），共2个。

解题思路详解

步骤1：理解问题本质

这是一个动态规划计数问题，我们需要统计原字符串中所有连续的有效括号子串的个数。
与“最长有效括号子串”问题（只求最长长度）不同，本题要求出所有可能子串的总数。

步骤2：动态规划状态定义

设 dp[i] 表示 以字符 s[i] 结尾的最长有效括号子串的长度。
这是经典“最长有效括号子串”问题中的状态定义，但这里我们需要用它来辅助计数。

为什么需要这个状态？
因为如果知道以 s[i] 结尾的最长有效括号子串长度，我们就可以推算出以 s[i] 结尾的所有有效括号子串的个数。

步骤3：状态转移方程推导

考虑 s[i]：

1. 如果 s[i] == '('，则 dp[i] = 0，因为以 '(' 结尾不可能是有效括号子串的结尾。
2. 如果 s[i] == ')'，则需要向前匹配：
   • 找到与当前 ')' 匹配的 '(' 的位置。
   • 设 j = i - dp[i-1] - 1，即跳过以 s[i-1] 结尾的最长有效括号子串，再向前一个位置。
   • 如果 j >= 0 且 s[j] == '('，则匹配成功：
     • 基础匹配长度 = dp[i-1] + 2
     • 如果匹配后，前面还有连续的有效括号子串（即 j-1 >= 0 且 dp[j-1] > 0），则可以连接起来。
     • 因此：

       dp[i] = dp[i-1] + 2 + (j-1 >= 0 ? dp[j-1] : 0)
       

   • 如果匹配失败，则 dp[i] = 0。

例子：s = "(())"，计算 dp：

• i=0: '(' → dp[0]=0
• i=1: '(' → dp[1]=0
• i=2: ')'，j = 2 - dp[1] - 1 = 1，s[1]='(' → 匹配成功，dp[2] = dp[1]+2 = 2
• i=3: ')'，j = 3 - dp[2] - 1 = 0，s[0]='(' → 匹配成功，dp[3] = dp[2]+2 + (j-1>=0? dp[-1]忽略) = 4

最终 dp = [0,0,2,4]。

步骤4：从 dp 数组得到答案

我们已经知道 dp[i] 是以 s[i] 结尾的最长有效括号子串长度。
那么，以 s[i] 结尾的所有有效括号子串的个数是多少呢？

观察规律：

• 如果 dp[i] > 0，说明以 s[i] 结尾有一个有效括号子串，其长度为 dp[i]。
• 并且，在这个最长有效子串内部，还包含若干更短的以 s[i] 结尾的有效子串。
• 实际上，以 s[i] 结尾的有效括号子串的个数等于 以 s[i] 结尾的最长有效括号子串中，包含多少个“后缀有效子串”。

更简单的方法：
设 count[i] 表示以 s[i] 结尾的有效括号子串的个数。
当 dp[i] > 0 时，我们知道这个最长子串是从位置 i - dp[i] + 1 到 i 的。
在这个最长子串中，以 s[i] 结尾的有效子串个数，就是最长子串内部所有能完整匹配到 s[i] 的后缀子串个数。

其实有一个更直接的发现：
如果 dp[i] > 0，那么以 s[i] 结尾的有效括号子串个数，等于以 s[i - dp[i]] 结尾的有效括号子串个数加1。
因为：

• 最长子串 s[i-dp[i]+1 ... i] 本身是一个有效子串。
• 此外，如果 i-dp[i] 位置之前还有有效子串，它们可以和当前最长子串拼接，形成新的以 s[i] 结尾的有效子串。

更简单的规律（经过验证）：

if dp[i] > 0:
    cnt[i] = 1 + (i - dp[i] >= 0 ? cnt[i - dp[i]] : 0)
else:
    cnt[i] = 0

然后答案 = 所有 cnt[i] 的和。

为什么？
因为以 s[i] 结尾的最长有效子串是 s[i-dp[i]+1 ... i]，这个子串内部，以 s[i] 结尾的有效子串可以通过“从最长子串的开头不断右移起始位置，但保持括号匹配”来得到。
实际上，这些子串正好对应：当前最长子串本身，以及前面紧邻的以 s[i-dp[i]] 结尾的所有有效子串拼接上当前最长子串。

例子：s = "()(())"，我们手动验证。

步骤5：逐步演算例子

以 s = "()(())" 为例，长度6。

1. 计算 dp：

   • i=0: '(' → 0
   • i=1: ')'，j=0，匹配，dp[1] = 0+2=2
   • i=2: '(' → 0
   • i=3: '(' → 0
   • i=4: ')'，j=3，匹配，dp[4] = 0+2=2
   • i=5: ')'，j=5-dp[4]-1=2，s[2]='('，匹配，dp[5]=dp[4]+2+dp[1]=2+2+2=6
     dp = [0,2,0,0,2,6]

2. 计算 cnt：

   • i=0: dp=0 → cnt=0
   • i=1: dp=2 → cnt[1] = 1 + (1-2>=0? cnt[-1]:0) = 1
   • i=2: dp=0 → 0
   • i=3: dp=0 → 0
   • i=4: dp=2 → cnt[4] = 1 + (4-2>=0? cnt[2]:0) = 1+0=1
   • i=5: dp=6 → cnt[5] = 1 + (5-6>=0? cnt[-1]:0) = 1
     cnt = [0,1,0,0,1,1]

3. 答案 = 0+1+0+0+1+1 = 3。

检查：有效括号子串有：

• "()" (0-1)
• "()" (4-5) 注意：这是内层的()，在(())中
• "()(())" (0-5)
  总共有3个，与计算结果一致。

步骤6：算法步骤总结

1. 初始化 dp 数组长度为 n，全0。
2. 遍历 i 从 0 到 n-1：
   • 如果 s[i] == ')'：
     • 计算 j = i - dp[i-1] - 1（如果 i-1 无效则 j=i-1）。
     • 如果 j >= 0 且 s[j] == '('：
       • dp[i] = dp[i-1] + 2
       • 如果 j-1 >= 0，则 dp[i] += dp[j-1]
3. 计算 cnt：
   • 如果 dp[i] > 0，cnt[i] = 1 + (i-dp[i] >= 0 ? cnt[i-dp[i]] : 0)
   • 否则 cnt[i] = 0
4. 答案 = 所有 cnt[i] 的和。

步骤7：复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(n)，用于存储 dp 和 cnt 数组（可优化到 O(1) 但代码复杂）。

步骤8：边界情况

• 空字符串：返回 0。
• 全为 '(' 或 ')'：返回 0。
• 嵌套与并列混合的括号：算法仍适用。

步骤9：代码实现（思路伪代码）

function countValidParenthesesSubstrings(s):
    n = s.length
    if n == 0: return 0
    dp = array of size n, filled with 0
    cnt = array of size n, filled with 0
    total = 0
    for i from 0 to n-1:
        if s[i] == ')':
            j = i - 1
            if i-1 >= 0:
                j = i - dp[i-1] - 1
            if j >= 0 and s[j] == '(':
                dp[i] = dp[i-1] + 2
                if j-1 >= 0:
                    dp[i] += dp[j-1]
        if dp[i] > 0:
            cnt[i] = 1
            if i - dp[i] >= 0:
                cnt[i] += cnt[i - dp[i]]
        total += cnt[i]
    return total

通过以上步骤，我们完成了从问题理解、状态设计、转移推导到最终计数的全过程。这个问题的关键在于利用“以 i 结尾的最长有效括号子串长度”来递推“以 i 结尾的所有有效括号子串个数”，从而得到总和。