好的，我将为你详细讲解一个不在你已提供列表中的线性动态规划题目。题目名称如下： 最长有效括号匹配子串的变种——统计所有有效的括号子串，并计算每个有效子串中嵌套的最大深度 题目描述 给你一个只包含字符 '(' 和 ')' 的字符串 s 。你需要解决一个进阶问题： 统计 字符串 s 中所有有效的括号子串（连续且有效的）的 个数 。 对于每一个找到的有效括号子串，计算其 最大嵌套深度 。例如， "(()())" 的最大嵌套深度为 2（最外层括号内又嵌套了一层）， "()" 的深度为 1， "((()))" 的深度为 3。 最终，你需要输出所有有效括号子串的 最大嵌套深度的总和 。 示例 1： 输入： s = "(()())" 解释： 有效括号子串有： "()" （深度1）， "()" （深度1， 从索引2开始的单个括号对）， "(()())" （深度2）。 总个数为 3。 深度总和 = 1 + 1 + 2 = 4。 输出： 4 示例 2： 输入： s = "(()(()))" 解释： 有效括号子串： "()" （深度1）， "()" （深度1）， "(()())" （深度2，由索引2到5组成）， "(()(()))" （深度3）。 深度总和 = 1 + 1 + 2 + 3 = 7。 输出： 7 约束条件： 1 <= s.length <= 10^4 s[i] 是 '(' 或 ')' 。 解题过程 这个题目可以看作经典“最长有效括号”问题的两个方向上的扩展：从求 一个最大值 变为 统计所有子串 ，并引入了 深度计算 。 我们使用 线性动态规划 ，核心是定义一个状态数组 dp 。 步骤 1：定义状态 我们定义 dp[i] 表示 以字符 s[i] 结尾的最长有效括号子串的长度 。这是解决经典问题的标准状态定义。 例如，对于 s = "(()())" ， dp[5] = 6 ，因为以索引5结尾的有效子串是整个字符串。 但是，仅凭 dp[i] 我们无法直接得到深度信息和所有子串的统计。我们需要在计算过程中进行累积。 步骤 2：状态转移方程（计算长度） 这是动态规划的核心逻辑。对于当前位置 i ： 如果 s[i] == '(' ，那么以 '(' 结尾不可能是有效子串的结束，所以 dp[i] = 0 。 如果 s[i] == ')' ，我们需要查看前面的字符来尝试匹配。 情况A： s[i-1] == '(' 。这形成了一个简单的括号对 "()" 。 转移方程： dp[i] = (i >= 2 ? dp[i-2] : 0) + 2 解释：在 i-1 和 i 形成一对后，我们可以将这对括号前面以 i-2 结尾的有效子串连接起来。 情况B： s[i-1] == ')' 。这表示我们可能遇到了 "......))" 的情况。我们需要检查与当前 ')' 对应的 '(' 的位置。 首先，找到以 i-1 结尾的有效子串的前一个位置： j = i - dp[i-1] - 1 。 如果 j >= 0 且 s[j] == '(' ，那么 s[j] 和 s[i] 形成了一对。 转移方程： dp[i] = dp[i-1] + 2 + (j > 0 ? dp[j-1] : 0) 解释： dp[i-1] 是 s[j+1 ... i-1] 这段有效子串的长度，加上新匹配的这对括号长度2，再加上这对括号之前（ j-1 结尾）的有效子串长度。 这个状态转移是求“最长有效括号”的标准解法，确保了 dp[i] 的正确性。 步骤 3：计算嵌套深度和统计子串 这是本题的关键创新点。我们不能在最后扫描 dp 数组再计算，而要在状态转移时 同步更新 我们的答案。 核心观察： 一个有效括号子串的 最大嵌套深度 ，等于这个子串在形成过程中， 未匹配的左括号栈的最大瞬时长度 。 对于 以 i 结尾的每一个有效子串 ，我们都可以在它被“闭合”（即计算完 dp[i] ）时，立即知道它的深度。 实现方法： 我们维护一个栈 stack ，但这次栈里存放的是 左括号的索引 。 初始化一个变量 total_depth_sum = 0 作为最终答案。 遍历字符串 s 的每个字符 s[i] ： 如果 s[i] == '(' ，将它的索引 i 压入栈中。此时，以这个 '(' 开始的潜在有效子串的深度增加了1。 如果 s[i] == ')' ，并且栈不为空（说明有可匹配的左括号）： 弹出栈顶元素，得到与之匹配的左括号索引 left_idx = stack.pop() 。 此刻，我们就找到了一个“闭合”的有效子串 ：这个子串从 left_idx 开始，到 i 结束。 这个子串的长度 len_sub = i - left_idx + 1 。我们之前计算的 dp[i] 应该等于这个长度（对于最长的以i结尾的子串），但这里我们通过栈直接得到了精确的起止点。 如何计算这个子串的深度？ 关键来了： 在弹出匹配的左括号 left_idx 之前，栈的当前大小（stack.size()）就代表了当前这个即将闭合的子串的嵌套深度！ 为什么？因为栈里存放的是所有尚未被匹配的左括号，而即将匹配的这个 left_idx 是在最深层的。所以 current_depth = stack.size() + 1 （+1 是因为即将弹出的这个左括号本身也贡献一层深度）。 将 current_depth 加到 total_depth_sum 中。 注意 ：这个子串内部可能包含多个更小的有效子串（例如 "(()())" 内部有两个 "()" ）。那些更小的子串，会在它们自己被闭合时（即遇到它们自己的 ')' 时）被单独计算并累加到 total_depth_sum 中。 示例推演（ s = "(()())" ）： i=0, s='(' : 栈= [0] i=1, s='(' : 栈= [0, 1] i=2, s=')' : 栈顶 left_idx=1 。弹出前栈大小=2，深度=2+1=3？等等，这里需要仔细理解。 实际上，当我们要匹配索引2的 ')' 和索引1的 '(' 时，栈里剩下的元素是 [0] 。这个 [0] 代表了 外层 的括号。所以，对于 s[1...2] = "()" 这个子串，它的嵌套深度应该是 外层左括号的数量 + 1 。外层左括号数量就是弹出匹配对之前栈的大小。此时栈大小=1。所以深度 = 1 (外层) + 1 (自身) = 2？不对， "()" 的深度应该是1。 纠正逻辑 ：深度应该是 当前有效括号对所在的层级 。更准确地说，当我们匹配 s[left_idx] 和 s[i] 时， 栈中剩余的元素个数，就是这对括号外部的层数 。因此，这对括号自身的深度是 外部层数 + 1 。 外部层数 = stack.size() （在弹出 left_idx 之前 ）。所以 深度 = stack.size() + 1 。 回到 i=2 ：弹出前 stack = [0, 1] ，大小=2。深度 = 2 + 1 = 3？这显然是错的，因为 "()" 深度为1。 发现了问题 ：我们的栈里存放的是所有未匹配的左括号索引。对于嵌套的 "(()" ，栈里有 [0,1] 。此时，索引1的 '(' 是内层，它即将被匹配。它的外部层数不应该是栈的大小，而是 在它之后入栈的左括号数量 ？不对，应该是 在它之前入栈且尚未匹配的左括号数量 。更简单的办法： 深度就是左括号被压入栈后，栈所达到的最大高度，对于这个即将闭合的对而言 。 修正且更简单的实现策略 ：我们不需要在匹配时复杂计算。我们可以维护另一个数组 depth[i] ，表示 字符串位置 i 所处的当前嵌套深度 。 遍历字符串，使用一个 current_depth 计数器。 遇到 '(' ， current_depth 加1，并记录 depth[i] = current_depth 。 遇到 ')' ， 先 记录 depth[i] = current_depth ，然后 current_depth 减1（如果 current_depth > 0 ）。 这样， depth[i] 就记录了每个字符的瞬时深度。 那么，对于一个从 l 到 r 的有效子串，它的最大深度就是 max(depth[l], depth[l+1], ..., depth[r]) 。但如何高效得到所有子串并求其最大深度呢？结合栈！ 最终正确且高效的方法（结合 dp 和 栈/深度数组）： 我们其实可以简化。目标是对每个闭合的有效括号对（代表一个以它结尾的最短有效基串）计算深度，并知道它扩展后形成的大子串会被自动分解计算。 使用栈，栈中元素为 (索引, 该左括号入栈时的深度) 。 遍历 i from 0 to n-1 ： 初始化一个变量 current_depth = 0 。 如果 s[i] == '(' ： current_depth += 1 栈.push( (i, current_depth) ) 如果 s[i] == ')' 且栈不为空： (left_idx, depth_at_left) = stack.pop() 此时， depth_at_left 就是刚刚弹出的这个左括号所处的深度，也正是由这个左括号和当前右括号形成的这个括号对所产生的“一层”深度。 但是，由这对括号作为 最外层 所形成的整个有效子串，其最大深度是多少？那就是从 left_idx 到 i 这个区间内，所有 左括号对应的深度 的最大值。而这个最大值，恰恰等于 depth_at_left 吗？不一定，例如 "(()())" ，最外层的左括号深度是1，但整个子串最大深度是2。 实际上，整个子串 [left_idx, i] 的最大深度，等于这个区间内所有 匹配成功的左括号 的深度的最大值。而这个信息，在我们 弹出栈时已经丢失了 。 因此，我们需要调整思路，采用一次扫描并利用 dp 数组辅助计算深度。 经过梳理，最清晰的解法如下： 我们分开两步，但都是O(n)： 第一步：计算 dp 数组 （如前所述），得到以每个位置结尾的最长有效括号长度。 第二步：计算深度贡献 。 再次遍历字符串。 当我们发现 dp[i] > 0 时，意味着以 i 结尾存在一个有效子串。这个子串的开始索引是 start = i - dp[i] + 1 。 我们需要计算子串 s[start...i] 的最大嵌套深度。我们可以用一次扫描，维护一个深度计数器 cnt 。 但更巧妙的是： 一个连续有效括号子串的最大深度，等于这个子串中，连续左括号的最大数量 。我们可以这样计算： 初始化 max_depth = 0, current_depth = 0 。 从 start 遍历到 i ： 如果 s[k] == '(' ，则 current_depth++ ，并更新 max_depth = max(max_depth, current_depth) 。 如果 s[k] == ')' ，则 current_depth-- 。 得到的 max_depth 就是这个子串的深度。 将 max_depth 加到总和中。 重要优化 ：我们不需要对每个有效子串都做内部遍历，那样最坏是O(n^2)。我们可以 预处理一个前缀深度数组 。 首先，遍历整个字符串 s ，得到数组 depth[i] ，表示遍历到 i 时的瞬时深度（遇到 '(' 则深度+1，遇到 ')' 且深度>0则深度-1）。 然后，对于任意区间 [l, r] ，该区间内的最大深度，等价于求 depth[l...r] 的最大值。这可以用 稀疏表（Sparse Table） 或 线段树 在O(1)或O(log n)时间内查询，但预处理需要O(n log n)。 对于本题，有更线性且简单的方法吗？有！ 我们只关心以每个位置 i 结尾的“最长”有效子串的深度 。当我们计算 dp[i] 时，我们已经知道这个子串的起始位置 j = i - dp[i] + 1 。我们可以在第一次遍历计算 dp 时， 同步维护一个数组 max_depth_until[i] ，它表示从字符串开头到 i 位置，所有 depth 值的最大值。但这不对，因为我们需要的是区间 [j, i] 的最大值。 最终线性解法 ：在计算 dp 的过程中，当我们确定一个有效子串 [j, i] 时，我们需要知道这个区间内 depth 的最大值。我们可以用 单调栈 的思想，但实现起来复杂。 考虑到清晰度和教学目的，我们采用一个 易于理解且对于10^4数据量可以接受 的O(n^2)最坏情况但平均很快的方法，并指出优化方向： 算法步骤总结： 计算 dp 数组（O(n)）。 初始化答案 total_sum = 0 。 遍历 i 从 0 到 n-1： 如果 dp[i] > 0 ： start = i - dp[i] + 1 。 计算子串 s[start..i] 的最大深度： 初始化 cur_depth = 0, max_depth = 0 。 对于 k 从 start 到 i ： 如果 s[k] == '(' ： cur_depth++ ， max_depth = max(max_depth, cur_depth) 。 否则（ s[k] == ')' ）： cur_depth-- 。 total_sum += max_depth 。 输出 total_sum 。 复杂度分析： 时间复杂度：计算 dp 为 O(n)。统计答案时，虽然有两层循环，但每个字符最多被作为 有效子串的末尾 计算一次深度，且在计算深度时，区间是连续且不重叠地（对于以不同 i 结尾的最长子串）扫描。实际上，所有深度计算扫描的字符总数和等于所有有效子串的长度和。最坏情况下（如 "(((...)))" ），有效子串个数为O(n)，每个长度O(n)，总和为O(n^2)。但在随机或一般数据下远好于此。 空间复杂度：O(n)，用于存储 dp 数组。 示例 s = "(()())" 的最终计算： dp = [0,0,2,0,0,6] i=2, dp[2]=2, start=1 , 子串 "( )" , max_depth=1 , sum=1 。 i=5, dp[5]=6, start=0 , 子串 "(()())" , 计算深度：遇到 '(' 深度1，再 '(' 深度2，遇到 ) 深度1， '(' 深度2， ) 深度1， ) 深度0。 max_depth=2 ， sum=1+2=3 。 还有以索引4结尾的子串吗？ dp[4]=0 。等等，我们漏掉了以索引3结尾的子串 "()" （从索引2到3）。我们的 dp 数组能捕捉到吗？检查： i=3, s='(' , dp[3]=0 。不对！ s[2..3]="()" 是有效的。问题出在哪里？ Bug 警示 ：我们定义 dp[i] 是 以 i 结尾的最长有效括号子串长度 。对于 i=3, s=')' ，我们应检查： s[2] == '(' ，属于情况A。所以 dp[3] = dp[1] + 2 = 0 + 2 = 2 。是的， dp[3] 应该是2，而不是0。我之前的示例 dp 数组给错了。 修正后的 dp = [0,0,2,2,0,6] 。 重新计算： i=2 : 子串 [1,2]="()" , depth=1 , sum=1 。 i=3 : 子串 [2,3]="()" , depth=1 , sum=2 。 i=5 : 子串 [0,5]="(()())" , depth=2 , sum=4 。 符合示例1输出4。 进一步的优化（O(n) 时间） 要实现严格的 O(n) 时间复杂度，我们需要在计算 dp[i] 时，也能 O(1) 得到对应子串的最大深度。 方法： 我们定义两个数组： dp_len[i] : 以 s[i] 结尾的最长有效括号子串 长度 （同上）。 dp_depth[i] : 以 s[i] 结尾的最长有效括号子串的 最大嵌套深度 。 状态转移方程（同时计算长度和深度）： s[i] == '(' ： dp_len[i] = 0 , dp_depth[i] = 0 。 s[i] == ')' ： 情况A ： s[i-1] == '(' 。 dp_len[i] = (i>=2 ? dp_len[i-2] : 0) + 2 。 dp_depth[i] = max( (i>=2 ? dp_depth[i-2] : 0), 1 ) 。为什么？因为新形成的 "()" 深度为1，我们要和前面子串的深度取最大值。 情况B ： s[i-1] == ')' 。令 j = i - dp_len[i-1] - 1 。 如果 j>=0 && s[j] == '(' ： dp_len[i] = dp_len[i-1] + 2 + (j>0 ? dp_len[j-1] : 0) 。 深度计算是关键 ：新形成的有效子串从 j 到 i 。它的深度等于： 内部子串 s[j+1...i-1] 的最大深度（即 dp_depth[i-1] ）。 再加上 新匹配的这对最外层括号所增加的一层深度 。但是，这对新括号的深度是多少？它是整个新子串的最外层，所以它的深度是1？不对，如果它外面还连接了别的有效子串（ dp[j-1] 部分），那么它的深度应该是外部子串深度+1。 正确的递推式： dp_depth[i] = max( dp_depth[i-1], (j>0 ? dp_depth[j-1] : 0) + 1 ) 。 解释：新子串的最大深度，要么是内部已有的最大深度（ dp_depth[i-1] ），要么是外部连接子串的深度加上新形成的这一层（ dp_depth[j-1] + 1 ），两者取较大值。 最后，我们需要的答案 total_sum 就是所有 dp_depth[i] 的和（因为对于每个以 i 结尾的 最长 有效子串，我们都计算了它的深度，并且所有有效子串都会作为某个 i 的最长子串被覆盖）。 这个O(n)的动态规划一次性解决了长度和深度，是最高效的解法。