线性动态规划：最长有效括号匹配子序列的变种——允许一次失配的最长有效括号子序列
字数 2359 2025-10-28 22:11:24

线性动态规划：最长有效括号匹配子序列的变种——允许一次失配的最长有效括号子序列

题目描述
给定一个仅由 '(' 和 ')' 组成的字符串 s，允许在匹配过程中最多出现一次“失配”（即一个括号可以匹配错误或不被匹配），求最长有效括号子序列的长度。
注意：子序列不要求连续，但相对顺序必须保留。例如，"()())" 的最长有效括号子序列（允许一次失配）为 4，对应子序列 "()()"。

解题思路
本题是经典“最长有效括号子序列”问题的变种，引入“最多一次失配”的条件后，需扩展状态设计来记录失配次数。
我们定义 dp[i][j][k]：

  • i 表示当前遍历到字符串的第 i 个字符（1-based 索引）。
  • j 表示当前未匹配的左括号数量（即栈深度）。
  • k 表示已使用的失配次数（0 或 1）。
    状态值表示在 s[0..i-1] 中，栈深度为 j、已使用 k 次失配时，能形成的最长有效括号子序列长度。

状态转移
对于每个字符 s[i-1] 和每个可能的 (j, k)，考虑三种决策：

  1. 跳过当前字符（视为失配，但仅当 k < 1 时可选择）：
    dp[i][j][k+1] = max(dp[i][j][k+1], dp[i-1][j][k])
  2. 选择当前字符，且能匹配：
    • 若 s[i-1] == '('，作为左括号加入：
      dp[i][j+1][k] = max(dp[i][j+1][k], dp[i-1][j][k] + 1)
    • 若 s[i-1] == ')' 且 j > 0，匹配一个左括号：
      dp[i][j-1][k] = max(dp[i][j-1][k], dp[i-1][j][k] + 2)
  3. 选择当前字符，但不能匹配（仅当 k < 1 时可选择）：
    • 若 s[i-1] == ')' 且 j == 0，无法匹配但允许失配：
      dp[i][0][k+1] = max(dp[i][0][k+1], dp[i-1][0][k])
    • 注：左括号失配已在“跳过”中覆盖，此处仅处理右括号失配。

初始化
dp[0][0][0] = 0，其余为负无穷（表示不可达）。

最终答案
遍历结束后，取所有 dp[n][0][k]（k=0,1）的最大值。

示例详解
以 s = "()())" 为例，演示部分状态转移：

  1. 初始：dp[0][0][0] = 0
  2. i=1, '('：
    • 选择作为左括号：dp[1][1][0] = 1
  3. i=2, ')'：
    • 从 (j=1,k=0) 匹配：dp[2][0][0] = max(0, 1+2=3)
    • 跳过（失配）：dp[2][1][1] = 1
  4. i=3, '('：
    • 从 (j=0,k=0) 加入左括号：dp[3][1][0] = 3+1=4
    • 从 (j=1,k=1) 加入左括号：dp[3][2][1] = 1+1=2
  5. i=4, ')'：
    • 从 (j=1,k=0) 匹配：dp[4][0][0] = 4+2=6（但实际不可能，因序列长度只有5，需检查边界）
    • 实际应取合理值：从 (j=1,k=0) 匹配得 dp[4][0][0]=4+2=6？重新计算：
      正确过程：
      • i=3 时，dp[3][1][0]=4 表示已选 "()("，长度3。
      • i=4 时，匹配 ')'：深度1→0，长度+2→5？但序列总长仅4，发现错误：长度记录的是子序列的括号对数×2，需调整理解。

修正理解
实际上，dp[i][j][k] 记录的是子序列中所有匹配括号对的总长度（即每对括号贡献2）。
最终答案应为 max(dp[n][0][k])，因为栈深度为0时所有左括号已匹配。

简化示例步骤（正确版本）：

  • i=1: '(' → dp[1][1][0]=0？不，应初始化长度为0，选择左括号时深度+1，长度不变（因为未形成对）。
    需重新定义：长度记录的是已匹配的括号对数×2，因此只有匹配成功时长度+2。

正确定义
dp[i][j][k]：前i个字符，栈深度j，失配次数k，已形成的匹配括号对数×2（即有效长度）。
转移：

  • 跳过：dp[i][j][k+1] = max(..., dp[i-1][j][k])
  • 选左括号：dp[i][j+1][k] = max(..., dp[i-1][j][k])（长度不变）
  • 选右括号且j>0：dp[i][j-1][k] = max(..., dp[i-1][j][k] + 2)
  • 选右括号且j=0且k<1：dp[i][0][k+1] = max(..., dp[i-1][0][k])

重新计算示例 s="()())"：

  1. i=1, '('：选→ dp[1][1][0]=0
  2. i=2, ')'：从(1,0)匹配→ dp[2][0][0]=0+2=2
  3. i=3, '('：选→ dp[3][1][0]=2
  4. i=4, ')'：从(1,0)匹配→ dp[4][0][0]=2+2=4
  5. i=5, ')'：
    • 从(0,0)匹配？j=0，不能匹配，但可失配：dp[5][0][1]=max(..., 4)=4
    • 或跳过（失配）：dp[5][0][1]=4
      最终答案 max(dp[5][0][0], dp[5][0][1]) = 4，符合预期。

复杂度分析

  • 时间复杂度：O(n²)，因为 j 的深度最多为 n。
  • 空间复杂度：可优化至 O(n) 使用滚动数组。

关键点

  • 状态设计涵盖索引、栈深度、失配次数。
  • 长度增加仅在匹配成功时发生。
  • 失配可用于跳过无法匹配的右括号或任意括号。
线性动态规划：最长有效括号匹配子序列的变种——允许一次失配的最长有效括号子序列 题目描述 给定一个仅由 '(' 和 ')' 组成的字符串 s ，允许在匹配过程中最多出现一次“失配”（即一个括号可以匹配错误或不被匹配），求最长有效括号子序列的长度。 注意：子序列不要求连续，但相对顺序必须保留。例如， "()())" 的最长有效括号子序列（允许一次失配）为 4，对应子序列 "()()" 。 解题思路 本题是经典“最长有效括号子序列”问题的变种，引入“最多一次失配”的条件后，需扩展状态设计来记录失配次数。 我们定义 dp[i][j][k] ： i 表示当前遍历到字符串的第 i 个字符（1-based 索引）。 j 表示当前未匹配的左括号数量（即栈深度）。 k 表示已使用的失配次数（0 或 1）。 状态值表示在 s[0..i-1] 中，栈深度为 j 、已使用 k 次失配时，能形成的最长有效括号子序列长度。 状态转移 对于每个字符 s[i-1] 和每个可能的 (j, k) ，考虑三种决策： 跳过当前字符 （视为失配，但仅当 k < 1 时可选择）： dp[i][j][k+1] = max(dp[i][j][k+1], dp[i-1][j][k]) 选择当前字符，且能匹配 ： 若 s[i-1] == '(' ，作为左括号加入： dp[i][j+1][k] = max(dp[i][j+1][k], dp[i-1][j][k] + 1) 若 s[i-1] == ')' 且 j > 0 ，匹配一个左括号： dp[i][j-1][k] = max(dp[i][j-1][k], dp[i-1][j][k] + 2) 选择当前字符，但不能匹配 （仅当 k < 1 时可选择）： 若 s[i-1] == ')' 且 j == 0 ，无法匹配但允许失配： dp[i][0][k+1] = max(dp[i][0][k+1], dp[i-1][0][k]) 注：左括号失配已在“跳过”中覆盖，此处仅处理右括号失配。 初始化 dp[0][0][0] = 0 ，其余为负无穷（表示不可达）。 最终答案 遍历结束后，取所有 dp[n][0][k] （ k=0,1 ）的最大值。 示例详解 以 s = "()())" 为例，演示部分状态转移： 初始 ： dp[0][0][0] = 0 i=1, '(' ： 选择作为左括号： dp[1][1][0] = 1 i=2, ')' ： 从 (j=1,k=0) 匹配： dp[2][0][0] = max(0, 1+2=3) 跳过（失配）： dp[2][1][1] = 1 i=3, '(' ： 从 (j=0,k=0) 加入左括号： dp[3][1][0] = 3+1=4 从 (j=1,k=1) 加入左括号： dp[3][2][1] = 1+1=2 i=4, ')' ： 从 (j=1,k=0) 匹配： dp[4][0][0] = 4+2=6 （但实际不可能，因序列长度只有5，需检查边界） 实际应取合理值：从 (j=1,k=0) 匹配得 dp[4][0][0]=4+2=6 ？重新计算： 正确过程： i=3 时， dp[3][1][0]=4 表示已选 "()(" ，长度3。 i=4 时，匹配 ')' ：深度1→0，长度+2→5？但序列总长仅4，发现错误： 长度记录的是子序列的括号对数×2 ，需调整理解。 修正理解 实际上， dp[i][j][k] 记录的是子序列中所有匹配括号对的总长度（即每对括号贡献2）。 最终答案应为 max(dp[n][0][k]) ，因为栈深度为0时所有左括号已匹配。 简化示例步骤 （正确版本）： i=1: '(' → dp[1][1][0]=0 ？不，应初始化长度为0，选择左括号时深度+1，长度不变（因为未形成对）。 需重新定义： 长度记录的是已匹配的括号对数×2 ，因此只有匹配成功时长度+2。 正确定义 dp[i][j][k] ：前i个字符，栈深度j，失配次数k， 已形成的匹配括号对数×2 （即有效长度）。 转移： 跳过： dp[i][j][k+1] = max(..., dp[i-1][j][k]) 选左括号： dp[i][j+1][k] = max(..., dp[i-1][j][k]) （长度不变） 选右括号且j>0： dp[i][j-1][k] = max(..., dp[i-1][j][k] + 2) 选右括号且j=0且k<1： dp[i][0][k+1] = max(..., dp[i-1][0][k]) 重新计算示例 s="()())" ： i=1, '('：选→ dp[1][1][0]=0 i=2, ')'：从(1,0)匹配→ dp[2][0][0]=0+2=2 i=3, '('：选→ dp[3][1][0]=2 i=4, ')'：从(1,0)匹配→ dp[4][0][0]=2+2=4 i=5, ')'： 从(0,0)匹配？j=0，不能匹配，但可失配： dp[5][0][1]=max(..., 4)=4 或跳过（失配）： dp[5][0][1]=4 最终答案 max(dp[5][0][0], dp[5][0][1]) = 4 ，符合预期。 复杂度分析 时间复杂度：O(n²)，因为 j 的深度最多为 n。 空间复杂度：可优化至 O(n) 使用滚动数组。 关键点 状态设计涵盖索引、栈深度、失配次数。 长度增加仅在匹配成功时发生。 失配可用于跳过无法匹配的右括号或任意括号。