区间动态规划例题：最长有效括号子串问题

题目描述
给定一个只包含字符 '(' 和 ')' 的字符串 s，要求找出其中最长的有效（格式正确）括号子串的长度。
有效括号子串需满足：

• 每个左括号 '(' 必须有对应的右括号 ')' 匹配。
• 子串内的括号匹配关系必须连续且正确（例如 "()()" 和 "(())" 均有效，但 "())" 无效）。

示例

• 输入：s = "(()"，输出：2（最长有效子串为 "()"）
• 输入：s = ")()())"，输出：4（最长有效子串为 "()()"）

解题思路
使用区间动态规划，定义 dp[i][j] 表示子串 s[i:j+1] 是否为有效括号子串。但直接记录布尔值无法高效计算最长长度，因此调整定义：
定义：dp[i] 表示以字符 s[i] 结尾的最长有效括号子串的长度。
关键观察：

1. 若 s[i] = '('，则以 '(' 结尾的子串必然无效，故 dp[i] = 0。
2. 若 s[i] = ')'，需检查前一个字符：
   • 情况1：s[i-1] = '('，形如 "...()"，则 dp[i] = dp[i-2] + 2（若 i-2 越界则取0）。
   • 情况2：s[i-1] = ')'，形如 "...))"，则需检查 s[i - dp[i-1] - 1] 是否为 '('：
     • 若是，则当前 ')' 与这个 '(' 匹配，此时 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]。

状态转移方程：

dp[i] = 0  # 初始化
if s[i] == ')':
    if i-1 >= 0 and s[i-1] == '(':
        dp[i] = (dp[i-2] if i-2 >= 0 else 0) + 2
    elif i-1 >= 0 and 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)

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

1. 初始化 dp = [0, 0, 0, 0, 0, 0]。
2. i=0：s[0]=')'，但前无字符，dp[0]=0。
3. i=1：s[1]='('，无效，dp[1]=0。
4. i=2：s[2]=')'，且 s[1]='('，属情况1：
   • dp[2] = dp[0] + 2 = 0 + 2 = 2。
5. i=3：s[3]='('，无效，dp[3]=0。
6. i=4：s[4]=')'，且 s[3]='('，属情况1：
   • dp[4] = dp[2] + 2 = 2 + 2 = 4。
7. i=5：s[5]=')'，且 s[4]=')'，属情况2：
   • j = 5 - dp[4] - 1 = 5 - 4 - 1 = 0，检查 s[0]=')'，不匹配，故 dp[5]=0。
8. 最终 max(dp) = 4，对应子串 "()()"。

复杂度分析

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

总结
通过定义以每个字符结尾的最长有效子串长度，利用前驱状态的信息，逐步推导出全局最优解。此方法避免了二维区间DP的高复杂度，是此类问题的经典优化思路。