线性动态规划：统计所有有效的括号子串，并计算每个有效子串中嵌套的最大深度

题目描述

给你一个只包含字符 '(' 和 ')' 的字符串 s，请你完成以下两个任务：

1. 统计该字符串中所有有效的括号子串的数量。
   有效括号子串定义为：该子串是原字符串的一个连续子串，且其中的括号能够完全匹配（每个左括号都有对应的右括号，且括号顺序正确）。

2. 对每个有效括号子串，计算出其嵌套的最大深度。
   括号嵌套深度定义如下：

   • 空字符串的深度为 0
   • 一个字符串的深度等于它的任意前缀中，'(' 的数量减去 ')' 的数量的最大值。

最后，需要输出所有有效括号子串的总个数，以及这些子串的深度总和。

示例
输入：s = "(()())"
解释：
有效括号子串有：

• "()" 深度 = 1
• "(())" 深度 = 2
• "()"（第二个，位于索引 2-3）深度 = 1
• "(()())" 深度 = 2
  总数 = 4，深度总和 = 1 + 2 + 1 + 2 = 6
  输出：[4, 6]

解题思路

这个问题可以分解为两个经典子问题的结合：

1. 找出所有有效的括号子串 → 类似 “最长有效括号” 的动态规划扩展。
2. 对每个有效子串计算其深度 → 可以在动态规划过程中一并计算。

步骤 1：定义状态

设 dp[i] 表示以字符 s[i] 结尾的最长有效括号子串的长度。
这是经典最长有效括号子串的 DP 定义。

但我们需要统计所有有效子串，而不仅仅是长度最大的那个。
因此还需要另一个量：

设 cnt[i] 表示以 s[i] 结尾的所有有效括号子串的数量。
但这样还不方便直接统计深度总和，所以我们需要进一步细化。

更好的设计：
定义 dp[i] 仍然是以 s[i] 结尾的最长有效括号子串长度，但我们可以利用它来推导出以每个位置结尾的所有有效括号子串的信息。

步骤 2：推导 dp[i] 的转移

经典最长有效括号子串的 DP 推导（只考虑 s[i] = ')' 的情况，因为只有右括号能结束有效串）：

• 如果 s[i] = ')' 且 s[i-1] = '('，则 dp[i] = dp[i-2] + 2（i-2 要大于等于 0，否则取 0）。
• 如果 s[i] = ')' 且 s[i-1] = ')'，则检查 j = i - dp[i-1] - 1：
  • 如果 j >= 0 且 s[j] = '('，则 dp[i] = dp[i-1] + 2 + (j-1 >= 0 ? dp[j-1] : 0)。

这个 dp[i] 可以告诉我们以 i 结尾的最长有效括号子串长度。一旦有了这个长度，我们就知道这个最长子串的起始位置是 i - dp[i] + 1。

步骤 3：统计所有有效子串

对于每个位置 i，如果 dp[i] > 0，那么以 i 结尾的有效括号子串可能有多个。
具体来说，假设以 i 结尾的最长有效子串是 s[start..i]，那么对于任意 k ∈ [start, i]，如果 s[k..i] 是有效括号串，那么它也是一个有效子串。
但如何高效找到所有这些子串？

关键观察：
如果 dp[i] > 0，那么我们可以从 i 向前跳，每次跳到一个匹配的左括号前一个位置，检查是否还有有效括号串。
但更好的办法是：我们可以在计算 dp[i] 的过程中，同时记录以 i 结尾的所有有效括号子串的数量，以及这些子串的深度总和。

步骤 4：增加计数和深度信息

我们定义两个数组：

• count[i]：以 s[i] 结尾的有效括号子串的数量。
• depth_sum[i]：以 s[i] 结尾的所有有效括号子串的深度总和。

计算方式：

情况 1：s[i] = ')' 且 s[i-1] = '('（形如 ...()）

此时，以 i 结尾的最短有效子串是 "()"，长度 2。
如果 i-2 >= 0，那么前面可能还连着另一个有效子串，组合成更长的串。

转移：

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

对于计数：
以 i 结尾的有效子串 = （以 i-2 结尾的有效子串每个后面加上 "()"） + 一个全新的 "()" 子串。
但注意，"()" 是一个新子串，而 (i-2 >= 0) 时，每个以 i-2 结尾的有效子串的末尾加上 "()" 会形成新的有效子串（长度增加 2）。
更简单的思路：
count[i] = 1 + (i-2 >= 0 ? count[i-2] : 0)
因为每个以 i-2 结尾的有效子串都可以扩展 2 个字符，仍然是有效子串，并且多了一个新的最短子串 "()"。

深度计算：
新子串 "()" 深度 = 1。
对于从 i-2 扩展来的子串，它们的深度等于原来深度 + 1（因为多了一层括号包裹）。
所以：

depth_sum[i] = 1 + (i-2 >= 0 ? depth_sum[i-2] + count[i-2] : 0)

这里 count[i-2] 是因为每个扩展来的子串深度都 +1。

情况 2：s[i] = ')' 且 s[i-1] = ')'（形如 ...))）

设 j = i - dp[i-1] - 1，如果 j >= 0 且 s[j] = '('，则 s[j+1..i-1] 是以 i-1 结尾的有效括号子串，长度为 dp[i-1]，然后与 s[j] 和 s[i] 匹配。

此时：

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

这表示：s[j+1..i-1] 是有效串，加上外层的 () 变成更长的串，再可能连接前面以 j-1 结尾的有效串。

计数：
以 i 结尾的有效子串包括：

1. 前面以 j-1 结尾的每个有效子串，扩展成 s[j..i] 的新子串。
2. 以 i-1 结尾的每个有效子串，加上外层括号变成新串。
3. 一个全新的子串 s[j..i]。

更严谨的推导：

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

因为：

• 新子串 s[j..i] 是 1 个。
• 以 i-1 结尾的每个有效子串，加上外层括号，仍是有效串，有 count[i-1] 个。
• 以 j-1 结尾的每个有效子串，后面接上新形成的 s[j..i]，形成更长串，有 count[j-1] 个。

深度总和：
新串 s[j..i] 深度 = 1 + 以 i-1 结尾的最长子串的深度？
更准确：新串深度 = 1 + 内部串 s[j+1..i-1] 的深度。
以 i-1 结尾的有效子串的深度信息我们需要记录。但注意，我们记录的是以某个位置结尾的所有有效子串的深度和，不是某一个子串的深度。
所以必须用公式推导：

设 inner_depth_sum 是 s[j+1..i-1] 的深度和，但它等于 depth_sum[i-1] 吗？不一定，因为 s[j+1..i-1] 是以 i-1 结尾的最长子串，但 depth_sum[i-1] 是所有以 i-1 结尾的有效子串的深度和。
我们需要的是最长子串的深度，不是所有子串的深度和。

这提示我们需要额外记录最长子串的深度。
因此我们增加：

• max_depth[i]：以 s[i] 结尾的最长有效括号子串的深度。

步骤 5：增加 max_depth[i] 的转移

情况 1：s[i] = ')' 且 s[i-1] = '('

max_depth[i] = 1

因为 "()" 深度为 1（即使前面有串，新形成的最长子串深度也是 1，因为外层括号只是一层）。

情况 2：s[i] = ')' 且 s[i-1] = ')' 且匹配成功

max_depth[i] = 1 + max_depth[i-1]

因为外层多了一层括号。

步骤 6：最终计数和深度总和公式

有了 max_depth[i]，我们就可以计算总深度和：

总深度和 = 每个有效子串的深度之和
我们可以用 depth_sum[i] 递推：

情况 1：s[i] = ')' 且 s[i-1] = '('

depth_sum[i] = 1 + (i-2 >= 0 ? depth_sum[i-2] + count[i-2] : 0)

解释：

• 1 是新子串 "()" 的深度。
• 从 i-2 扩展来的每个子串，深度都 +1，所以加 count[i-2]。

情况 2：s[i] = ')' 且 s[i-1] = ')' 且匹配成功

depth_sum[i] = (1 + max_depth[i-1])  // 新子串 s[j..i] 的深度
               + (depth_sum[i-1] + count[i-1])  // 从 i-1 扩展来的子串，深度+1
               + (j-1 >= 0 ? depth_sum[j-1] + count[j-1] : 0)  // 从 j-1 扩展来的子串，深度+1

这里第一项是新子串的深度，后面是扩展子串的深度增加。

步骤 7：最终求和

最终答案：

• 总有效子串数 = 所有 count[i] 的和（i 从 0 到 n-1）。
• 总深度和 = 所有 depth_sum[i] 的和。

初始化：所有数组初始为 0。

步骤 8：举例推导

以 s = "(()())" 为例（索引从 0 开始）：

验证：

• 总有效子串数 = 1+1+4 = 6？等等，我们多算了，因为有些子串被重复计算了吗？
  注意：count[i] 是以 i 结尾的有效子串数，不同结尾的子串是不同的，所以总子串数 = 1+1+4=6，但原题例子是 4，为什么？
  因为我们的定义中，有效子串是连续子串，且以 i 结尾的子串可能在更早的 i 也被算作另一个结尾的子串的一部分吗？不，每个子串有唯一的结尾位置。
  但例子中 "()" 出现了两次，分别是结尾在 2 和结尾在 4，确实不同子串。但为什么例子是 4？
  我明白了，例子中给出的 "(()())" 的有效子串是："()"(2-3), "(())"(1-4), "()"(4-5), "(()())"(0-5)，共 4 个。
  我们算出来 6 个，多出的 2 个是什么？
  检查我们的递推：
  i=5 时，count[5]=4 表示以 5 结尾的 4 个子串：
  1. "(()())" (0-5)
  2. "()" (4-5)
  3. "(())" (1-4) 加上 ")"(5) 不是有效串，所以这个不对，说明我们的计数公式在情况 2 有误。

这里我们发现，情况 2 的计数公式 count[i] = 1 + count[i-1] + (j-1>=0?count[j-1]:0) 是错误的，因为它重复计算了。
实际上，以 i 结尾的有效子串是唯一的，就是 s[i-dp[i]+1 .. i] 这个最长串，以及它的后缀有效子串？不，有效括号子串的后缀不一定是有效的。

所以正确方法更简单：
以 i 结尾的有效括号子串就是那些 s[k..i] 是有效串的 k。
我们可以从 i 向前跳，每次跳到当前有效串的开始的前一个位置，看是否还有有效串。但这样是 O(n²)。
为了 O(n)，我们可以用栈+DP：

步骤 9：更简洁的方法

我们只需要计算：
dp[i] 表示以 i 结尾的最长有效括号子串长度。
然后，对于每个 i，如果 dp[i] > 0，那么这个最长串内部可能包含若干有效子串，这些子串的结尾也在 i 吗？不一定。
我们最终要统计的是所有有效子串，不只是以某个位置结尾的。

所以更直接的思路：
用栈保存未匹配的左括号下标，遇到右括号匹配时，弹出栈顶，此时当前有效子串的起始位置是栈顶的下一个位置（栈空则为 0）。
在匹配时，我们可以计算这个有效子串的深度，并累加计数。

但题目要求：所有有效子串的深度总和。
我们可以这样：
当匹配到一对括号时，以当前右括号结尾的有效子串可能有多个，但它们的深度可以通过前缀平衡数计算。
不过，每个子串的深度，等于这个子串的任意前缀中左括号比右括号多的最大值。这可以在栈中维护深度信息。

但这样需要枚举所有子串，会 O(n²)。

为了 O(n)，可以用 DP 直接计算每个位置结尾的有效子串的深度和。
实际上，更简单的公式是：
设 depth_sum[i] 表示以 i 结尾的所有有效子串的深度总和。
那么：

• 如果形成 ...()，则 depth_sum[i] = 1 + (i-2>=0 ? depth_sum[i-2] : 0)
• 如果形成 ...((...))，则 depth_sum[i] = (1 + max_depth[i-1]) + depth_sum[i-1] 吗？

为了避免复杂化，我们换一个思路：

步骤 10：最终简洁方案

我们只需计算：

1. 总有效子串数 = 对所有 i，如果 dp[i] > 0，则加上 dp[i]/2 个以 i 结尾的有效子串？不对，这样会重复计算。
   实际上，以 i 结尾的有效子串的数量 = 以 i 结尾的最长有效子串的长度除以 2 吗？也不是。

   更好的方法：
   我们定义 valid[i] 表示以 i 结尾的有效子串的数量。
   如果 s[i] = ')' 且能与前面的 '(' 匹配，设匹配的左括号下标是 j，则：

   valid[i] = 1 + valid[j-1]  (如果 j-1 >=0)
   

   因为：

   • 新的有效子串 s[j..i]
   • 再加上以 j-1 结尾的每个有效子串，后面接上 s[j..i]，形成新的有效子串（因为括号匹配的扩展）。

   这样，valid[i] 就是以 i 结尾的有效子串数。
   总有效子串数 = 所有 valid[i] 的和。

2. 深度总和：
   设 depth_sum[i] 是以 i 结尾的所有有效子串的深度总和。
   深度计算：新子串 s[j..i] 的深度 = 1 + 内部串的深度。
   内部串是 s[j+1..i-1]，它的深度是 max_depth[i-1]（以 i-1 结尾的最长子串的深度）。
   所以新子串深度 = 1 + max_depth[i-1]。
   从 j-1 扩展来的子串，深度增加 1。
   所以：

   depth_sum[i] = (1 + max_depth[i-1]) + depth_sum[j-1] + valid[j-1]
   

   这里 valid[j-1] 是因为每个扩展子串深度 +1。

   初始：max_depth[i] = 1 + max_depth[i-1]（如果内部有效的话）。

步骤 11：算法步骤

1. 初始化 dp[n] = 0, valid[n] = 0, max_depth[n] = 0, depth_sum[n] = 0。
2. 遍历 i 从 0 到 n-1：
   • 如果 s[i] = '('，跳过（因为右括号才可能结束有效串）。
   • 如果 s[i] = ')'：
     • 如果 i-1 >= 0 且 s[i-1] = '('：
       j = i-1
valid[i] = 1 + (j-1 >= 0 ? valid[j-1] : 0)
max_depth[i] = 1
depth_sum[i] = 1 + (j-1 >= 0 ? depth_sum[j-1] + valid[j-1] : 0)
     • 否则如果 i-1 >= 0 且 s[i-1] = ')'：
       如果 dp[i-1] > 0，则 j = i - dp[i-1] - 1，否则 j = i-1 不匹配。
       如果 j >= 0 且 s[j] = '('：
       valid[i] = 1 + (j-1 >= 0 ? valid[j-1] : 0)
max_depth[i] = 1 + max_depth[i-1]
depth_sum[i] = (1 + max_depth[i-1]) + (j-1 >= 0 ? depth_sum[j-1] + valid[j-1] : 0)
3. 总有效子串数 = sum(valid[i])
   总深度和 = sum(depth_sum[i])

步骤 12：示例验证

s = "(()())"
i=2: s[2]=')'，s[1]='(' → j=1
valid[2]=1+valid[0]=1
max_depth[2]=1
depth_sum[2]=1

i=4: s[4]=')'，s[3]='(' → j=3
valid[4]=1+valid[2]=1+1=2
max_depth[4]=1
depth_sum[4]=1+(depth_sum[2]+valid[2])=1+(1+1)=3

i=5: s[5]=')'，s[4]=')'，dp[4]=2，j=5-2-1=2，s[2]='(' ✅
valid[5]=1+valid[1]=1+0=1
max_depth[5]=1+max_depth[4]=1+1=2
depth_sum[5]=(1+1)+(depth_sum[1]+valid[1])=2+0=2

总和：
valid_sum = 1+2+1=4 ✅
depth_sum_total = 1+3+2=6 ✅

结果与示例一致。

最终实现

def count_valid_parentheses_and_depth(s: str):
    n = len(s)
    dp = [0] * n
    valid = [0] * n
    max_depth = [0] * n
    depth_sum = [0] * n
    
    total_valid = 0
    total_depth_sum = 0
    
    for i in range(n):
        if s[i] == ')':
            if i-1 >= 0 and s[i-1] == '(':
                j = i-1
                valid[i] = 1 + (j-1 >= 0 and dp[j-1] > 0 and valid[j-1] or 0)
                max_depth[i] = 1
                depth_sum[i] = 1 + (j-1 >= 0 and dp[j-1] > 0 and (depth_sum[j-1] + valid[j-1]) or 0)
                dp[i] = 2 + (j-1 >= 0 and dp[j-1] or 0)
            elif i-1 >= 0 and s[i-1] == ')':
                if dp[i-1] > 0:
                    j = i - dp[i-1] - 1
                    if j >= 0 and s[j] == '(':
                        valid[i] = 1 + (j-1 >= 0 and dp[j-1] > 0 and valid[j-1] or 0)
                        max_depth[i] = 1 + max_depth[i-1]
                        depth_sum[i] = (1 + max_depth[i-1]) + (j-1 >= 0 and dp[j-1] > 0 and (depth_sum[j-1] + valid[j-1]) or 0)
                        dp[i] = dp[i-1] + 2 + (j-1 >= 0 and dp[j-1] or 0)
        
        total_valid += valid[i]
        total_depth_sum += depth_sum[i]
    
    return [total_valid, total_depth_sum]