线性动态规划：最长有效括号匹配子序列长度
字数 2468 2025-10-27 08:13:40

线性动态规划：最长有效括号匹配子序列长度

题目描述
给定一个只包含 '(' 和 ')' 的字符串 s，找出最长的有效括号匹配子序列的长度。注意：子序列不要求连续，但要求相对顺序不变，且每个左括号必须有对应的右括号匹配。

例如：
s = "()())" 的最长有效括号子序列是 "()()"，长度为 4。
s = ")(()())" 的最长有效括号子序列是 "(()())"，长度为 6。

解题思路
这个问题是最长有效括号匹配子序列（Longest Valid Parentheses Subsequence），不同于连续子串问题，它允许跳过部分字符。我们可以使用线性动态规划解决，定义 dp[i][j] 为子串 s[i:j] 的最长有效括号子序列长度，但更高效的方法是使用一维 DP 或栈辅助计数。

这里我们采用一维 DP，定义 dp[i] 表示以 i 结尾的子串中，最长有效括号子序列的长度。但直接这样定义不方便，因为括号匹配是成对的，我们考虑用栈+DP结合的方式。

步骤 1：问题分析
有效括号序列的充要条件：

  1. 左右括号数量相等；
  2. 任意前缀中左括号数不少于右括号数。

对于子序列问题，我们需要选择一些括号，使得选出的序列是有效的。关键点：每个右括号必须匹配一个在它之前且未被匹配的左括号。

步骤 2：动态规划定义
定义 dp[i] 表示前 i 个字符中，最长有效括号子序列的长度。
我们还需要一个辅助变量 left_count，表示在当前选择中，尚未匹配的左括号的数量。

但这样还不够，因为子序列可以跳过字符，我们需要知道之前有哪些左括号可以被匹配。
更标准的解法：
定义 dp[i][j] 为前 i 个字符中，选取若干字符形成子序列，且该子序列中未匹配的左括号数为 j 时的最大长度（j ≥ 0）。
那么答案就是 dp[n][0]（所有左括号都匹配完）。

步骤 3：状态转移
对于每个字符 s[i]（索引从 1 开始）：

  • 如果 s[i] 是 '('：
    1. 不选这个字符：dp[i][j] = dp[i-1][j]
    2. 选这个字符：那么未匹配左括号数会变成 j+1，长度+1，所以 dp[i][j+1] = max(dp[i][j+1], dp[i-1][j] + 1)
  • 如果 s[i] 是 ')'：
    1. 不选：dp[i][j] = dp[i-1][j]
    2. 选：只有当 j > 0（有未匹配的左括号）时，才能选这个右括号，匹配掉一个左括号，未匹配数变成 j-1，长度+1，所以 dp[i][j-1] = max(dp[i][j-1], dp[i-1][j] + 1)

初始化：dp[0][0] = 0，其他 dp[0][j] = -inf（不可达）。

步骤 4：简化为一维 DP
因为 dp[i] 只依赖于 dp[i-1]，可以滚动数组优化空间。
我们只需两个数组：prev[j] 和 curr[j]，分别表示前 i-1 个字符和前 i 个字符的状态。

步骤 5：示例推导
以 s = "()())" 为例（n=5）：
初始化：prev[0]=0，其他 prev[j]=-inf。

i=1: '('
选：curr[1] = prev[0]+1 = 1
不选：curr[0] = prev[0] = 0
所以 prev 更新为：prev[0]=0, prev[1]=1, 其他 -inf。

i=2: ')'
j=0: 选不了 ')'（因为 j=0 无左括号匹配），所以 curr[0] = prev[0]=0
j=1: 选')'：curr[0] = max(curr[0], prev[1]+1)=max(0,2)=2
不选：curr[1] = prev[1]=1
所以 prev: prev[0]=2, prev[1]=1。

i=3: '('
j=0: 选'('：curr[1] = prev[0]+1=3
不选：curr[0] = prev[0]=2
j=1: 选'('：curr[2] = prev[1]+1=2
不选：curr[1] = max(curr[1], prev[1])=max(3,1)=3
所以 prev: prev[0]=2, prev[1]=3, prev[2]=2。

i=4: ')'
j=0: 不能选')'，curr[0]=prev[0]=2
j=1: 选')'：curr[0]=max(2, prev[1]+1)=max(2,4)=4
j=2: 选')'：curr[1]=max(curr[1], prev[2]+1)=max(?,3)=3（curr[1] 初始为 prev[1]=3）
不选：curr[1]=max(3,3)=3, curr[2]=prev[2]=2
所以 prev: prev[0]=4, prev[1]=3, prev[2]=2。

i=5: ')'
j=0: 不能选')'，curr[0]=4
j=1: 选')'：curr[0]=max(4, 3+1)=4
j=2: 选')'：curr[1]=max(3, 2+1)=3
所以最终 prev[0]=4 为答案。

步骤 6：算法实现要点

  • 因为 j 的范围最大为 n，所以空间 O(n)。
  • 时间 O(n²) 因为 j 最多 n。
  • 实际 j 的范围可以限制到当前可能的最大未匹配左括号数（即到当前位置的 '(' 数量）。

总结
这个问题通过 DP 状态 j 记录未匹配左括号数，从而能够处理子序列匹配问题。每一步根据当前字符是左括号还是右括号，决定是否选择并更新状态。最终 dp[n][0] 就是所有字符考虑完后，完全匹配的最长有效括号子序列长度。

线性动态规划：最长有效括号匹配子序列长度 题目描述 给定一个只包含 '(' 和 ')' 的字符串 s，找出最长的有效括号匹配子序列的长度。注意：子序列不要求连续，但要求相对顺序不变，且每个左括号必须有对应的右括号匹配。 例如： s = "()())" 的最长有效括号子序列是 "()()"，长度为 4。 s = ")(()())" 的最长有效括号子序列是 "(()())"，长度为 6。 解题思路 这个问题是 最长有效括号匹配子序列 （Longest Valid Parentheses Subsequence），不同于连续子串问题，它允许跳过部分字符。我们可以使用 线性动态规划 解决，定义 dp[ i][ j] 为子串 s[ i:j ] 的最长有效括号子序列长度，但更高效的方法是使用一维 DP 或栈辅助计数。 这里我们采用 一维 DP ，定义 dp[ i] 表示以 i 结尾的子串中，最长有效括号子序列的长度。但直接这样定义不方便，因为括号匹配是成对的，我们考虑用 栈+DP 结合的方式。 步骤 1：问题分析 有效括号序列的充要条件： 左右括号数量相等； 任意前缀中左括号数不少于右括号数。 对于子序列问题，我们需要选择一些括号，使得选出的序列是有效的。关键点： 每个右括号必须匹配一个在它之前且未被匹配的左括号 。 步骤 2：动态规划定义 定义 dp[ i ] 表示前 i 个字符中，最长有效括号子序列的长度。 我们还需要一个辅助变量 left_ count，表示在当前选择中，尚未匹配的左括号的数量。 但这样还不够，因为子序列可以跳过字符，我们需要知道之前有哪些左括号可以被匹配。 更标准的解法： 定义 dp[ i][ j ] 为前 i 个字符中，选取若干字符形成子序列，且该子序列中未匹配的左括号数为 j 时的最大长度（j ≥ 0）。 那么答案就是 dp[ n][ 0 ]（所有左括号都匹配完）。 步骤 3：状态转移 对于每个字符 s[ i ]（索引从 1 开始）： 如果 s[ i ] 是 '('： 不选 这个字符：dp[ i][ j] = dp[ i-1][ j ] 选 这个字符：那么未匹配左括号数会变成 j+1，长度+1，所以 dp[ i][ j+1] = max(dp[ i][ j+1], dp[ i-1][ j ] + 1) 如果 s[ i ] 是 ')'： 不选 ：dp[ i][ j] = dp[ i-1][ j ] 选 ：只有当 j > 0（有未匹配的左括号）时，才能选这个右括号，匹配掉一个左括号，未匹配数变成 j-1，长度+1，所以 dp[ i][ j-1] = max(dp[ i][ j-1], dp[ i-1][ j ] + 1) 初始化：dp[ 0][ 0] = 0，其他 dp[ 0][ j ] = -inf（不可达）。 步骤 4：简化为一维 DP 因为 dp[ i] 只依赖于 dp[ i-1 ]，可以滚动数组优化空间。 我们只需两个数组：prev[ j] 和 curr[ j ]，分别表示前 i-1 个字符和前 i 个字符的状态。 步骤 5：示例推导 以 s = "()())" 为例（n=5）： 初始化：prev[ 0]=0，其他 prev[ j ]=-inf。 i=1: '(' 选：curr[ 1] = prev[ 0 ]+1 = 1 不选：curr[ 0] = prev[ 0 ] = 0 所以 prev 更新为：prev[ 0]=0, prev[ 1 ]=1, 其他 -inf。 i=2: ')' j=0: 选不了 ')'（因为 j=0 无左括号匹配），所以 curr[ 0] = prev[ 0 ]=0 j=1: 选')'：curr[ 0] = max(curr[ 0], prev[ 1 ]+1)=max(0,2)=2 不选：curr[ 1] = prev[ 1 ]=1 所以 prev: prev[ 0]=2, prev[ 1 ]=1。 i=3: '(' j=0: 选'('：curr[ 1] = prev[ 0 ]+1=3 不选：curr[ 0] = prev[ 0 ]=2 j=1: 选'('：curr[ 2] = prev[ 1 ]+1=2 不选：curr[ 1] = max(curr[ 1], prev[ 1 ])=max(3,1)=3 所以 prev: prev[ 0]=2, prev[ 1]=3, prev[ 2 ]=2。 i=4: ')' j=0: 不能选')'，curr[ 0]=prev[ 0 ]=2 j=1: 选')'：curr[ 0]=max(2, prev[ 1 ]+1)=max(2,4)=4 j=2: 选')'：curr[ 1]=max(curr[ 1], prev[ 2]+1)=max(?,3)=3（curr[ 1] 初始为 prev[ 1 ]=3） 不选：curr[ 1]=max(3,3)=3, curr[ 2]=prev[ 2 ]=2 所以 prev: prev[ 0]=4, prev[ 1]=3, prev[ 2 ]=2。 i=5: ')' j=0: 不能选')'，curr[ 0 ]=4 j=1: 选')'：curr[ 0 ]=max(4, 3+1)=4 j=2: 选')'：curr[ 1 ]=max(3, 2+1)=3 所以最终 prev[ 0 ]=4 为答案。 步骤 6：算法实现要点 因为 j 的范围最大为 n，所以空间 O(n)。 时间 O(n²) 因为 j 最多 n。 实际 j 的范围可以限制到当前可能的最大未匹配左括号数（即到当前位置的 '(' 数量）。 总结 这个问题通过 DP 状态 j 记录未匹配左括号数，从而能够处理子序列匹配问题。每一步根据当前字符是左括号还是右括号，决定是否选择并更新状态。最终 dp[ n][ 0 ] 就是所有字符考虑完后，完全匹配的最长有效括号子序列长度。