最长有效括号匹配子序列的变种：允许一次失配的最长有效括号子序列 题目描述 给定一个由 '(' 和 ')' 组成的字符串 s，你可以选择最多一个位置将其字符修改成相反的括号（也可以不修改），然后找出最长的有效括号子序列的长度。有效括号子序列不要求连续，但必须满足括号匹配规则。 解题思路 这个问题是经典最长有效括号子序列（不要求连续）的变种，增加了一次修改的机会。我们可以通过动态规划来记录状态，其中状态需要包含当前未匹配的左括号数量以及是否已经使用过修改机会。 详细步骤 状态定义 定义 dp[ i][ j][ k ] 表示考虑前 i 个字符，当前未匹配的左括号数量为 j，是否使用过修改机会（k=0 表示未使用，k=1 表示已使用）时的最长有效括号子序列长度。 初始化 dp[ 0][ 0][ 0 ] = 0，其他初始为负无穷（表示不可达状态）。 状态转移 对于每个位置 i（从1开始）和每个可能的未匹配左括号数 j，以及 k=0 或 1： 不选当前字符 ：状态直接继承，即 dp[ i][ j][ k] = max(dp[ i][ j][ k], dp[ i-1][ j][ k ]) 选择当前字符 ：有两种情况： 不修改当前字符 ： 如果 s[ i-1 ] 是 '('：选择后未匹配左括号数变为 j+1，长度+1 如果 s[ i-1 ] 是 ')'：如果 j>0，选择后未匹配左括号数变为 j-1，长度+1；否则不能选择 修改当前字符 （仅当 k=0 时可用）： 修改后字符取反，然后同样根据修改后的字符是 '(' 还是 ')' 进行转移，同时将 k 置为 1 最终答案 所有 dp[ n][ 0][ k ]（k=0或1）中的最大值，即最终未匹配左括号数为0的状态。 示例演示 以 s = "())" 为例： 不修改：最长有效子序列为 "()" 长度2 修改最后一个字符：变成 "()(" 或 "())"？实际上修改第二个 ')' 为 '(' 得到 "()(" 无效，但修改第一个 ')' 为 '(' 得到 "(())" 有效？注意这里是子序列不要求连续，所以可以通过选择字符得到更优解。 通过这个动态规划过程，我们可以高效求出允许一次修改时的最长有效括号子序列长度。