线性动态规划：最长有效括号匹配子串的动态规划解法

题目描述

给定一个只包含字符 '(' 和 ')' 的字符串 s，请你找出最长有效（格式正确且连续）括号子串的长度。

有效括号字符串的定义：

• 空字符串是有效的
• 如果字符串 A 是有效的，那么 (A) 也是有效的
• 如果字符串 A 和 B 是有效的，那么 AB 也是有效的

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

解题思路

我们采用动态规划来解决这个问题。动态规划的核心是定义状态，并找到状态转移方程。

步骤 1：定义状态

设 dp[i] 表示以字符 s[i] 结尾的最长有效括号子串的长度。

注意：有效括号子串必须以 ')' 结尾，因为如果以 '(' 结尾，它不可能是有效的。所以对于 s[i] = '('，我们有 dp[i] = 0。

步骤 2：状态转移分析

我们考虑字符串 s 的每个位置 i：

情况 1：s[i] = '('

• 以 '(' 结尾的子串不可能是有效的，所以 dp[i] = 0。

情况 2：s[i] = ')'
这里又可以分为两种子情况：

子情况 2.1：s[i-1] = '('

• 字符串形如 "...()"，那么 dp[i] = dp[i-2] + 2，其中 dp[i-2] 是 s[i-2] 结尾的最长有效长度（如果 i-2 越界，则视为 0）。

示例："()"

• i=1，s[1]=')'，s[0]='('，dp[1] = dp[-1] + 2 = 0 + 2 = 2

子情况 2.2：s[i-1] = ')'

• 字符串形如 "...))"，这时我们需要检查与当前 ')' 匹配的 '(' 的位置。
• 假设以 s[i-1] 结尾的有效子串长度为 dp[i-1]，那么与 s[i] 对应的可能 '(' 位置是 j = i - dp[i-1] - 1。
• 如果 j >= 0 且 s[j] = '('，那么我们可以形成一个更长的有效子串：

  dp[i] = dp[i-1] + 2 + dp[j-1]
  

  其中：
  • dp[i-1] 是以 s[i-1] 结尾的有效长度
  • +2 是新增的一对括号 ( 和 )
  • + dp[j-1] 是 j-1 位置结尾的有效长度（如果 j-1 越界则为 0）

示例："()(())"

• 当 i=5，s[5]=')'，s[4]=')'，dp[4]=2（子串 "()" 在位置 3,4）
• j = 5 - dp[4] - 1 = 5 - 2 - 1 = 2，s[2]='('，匹配成功
• dp[5] = dp[4] + 2 + dp[1] = 2 + 2 + 2 = 6（整个字符串）

步骤 3：状态转移方程总结

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

步骤 4：初始化与边界处理

• 如果字符串为空或长度为 1，答案直接为 0
• 可以初始化 dp 数组全为 0，长度为 n
• 注意数组越界判断

步骤 5：计算过程示例

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

最长值为 4，对应子串 "()()"（位置 1~4）。

步骤 6：实现细节

• 遍历 i 从 0 到 n-1
• 每次更新 dp[i] 后，更新全局最大值
• 时间复杂度 O(n)，空间复杂度 O(n)（可优化为 O(1) 但较复杂）

代码实现（Python）

def longestValidParentheses(s: str) -> int:
    n = len(s)
    if n < 2:
        return 0
    
    dp = [0] * n
    max_len = 0
    
    for i in range(1, n):
        if s[i] == ')':
            if s[i-1] == '(':  # 情况 "...()"
                dp[i] = (dp[i-2] if i >= 2 else 0) + 2
            else:  # 情况 "...))"
                j = i - dp[i-1] - 1
                if j >= 0 and s[j] == '(':
                    dp[i] = dp[i-1] + 2 + (dp[j-1] if j >= 1 else 0)
            max_len = max(max_len, dp[i])
    
    return max_len

关键点总结

1. 状态定义：dp[i] 是以 s[i] 结尾的最长有效括号子串长度
2. 两种情况：根据 s[i] 和 s[i-1] 的值分别处理
3. 匹配位置计算：在 "...))" 情况下，通过 j = i - dp[i-1] - 1 找到可能的匹配左括号位置
4. 连接之前有效段：匹配成功后，不要忘记加上 dp[j-1] 部分

这个动态规划解法一次遍历即可得到结果，是解决此类问题的经典方法。