线性动态规划：最长有效括号匹配子序列的变种——允许最多k次失配的最长有效括号子序列（进阶版：失配位置可修复） 题目描述 给定一个由 '(' 和 ')' 组成的字符串 s ，以及一个整数 k （ k ≥ 0 ）。定义一种特殊的括号子序列：允许在最多 k 个位置上出现失配（即该位置的括号不匹配），但可以通过一次“修复”操作（例如翻转括号）使其变为完全匹配的有效括号子序列。求满足该条件的最长子序列的长度。 关键点 子序列不要求连续，但需保留原顺序。 失配位置指在该子序列中，某个左括号 ')' 没有对应的右括号 '('，或反之。 “修复”操作在本题中隐含允许失配位置被修正，因此问题转化为：找一个最长子序列，其失配位置数 ≤ k。 解题思路 使用动态规划，定义状态 dp[i][j][d] ： i ：考虑字符串 s 的前 i 个字符。 j ：当前子序列中未匹配的左括号数量（即栈深度）。 d ：当前已使用的失配次数（0 ≤ d ≤ k）。 值 dp[i][j][d] 表示在满足上述条件时的最长子序列长度。 状态转移 对于每个字符 s[i-1] （索引从1开始），有两种选择： 不选当前字符 ：直接继承前一个状态： dp[i][j][d] = max(dp[i][j][d], dp[i-1][j][d]) 选当前字符 ： 若当前是 '('：加入后未匹配左括号数增1，深度变为 j+1 ，失配次数不变。 dp[i][j+1][d] = max(dp[i][j+1][d], dp[i-1][j][d] + 1) 若当前是 ')'： 情况1 ：有未匹配的左括号（j > 0），则匹配成功，深度减1： dp[i][j-1][d] = max(dp[i][j-1][d], dp[i-1][j][d] + 1) 情况2 ：无左括号匹配（j = 0），则视为失配，但可通过修复操作转为左括号（需 d < k）： dp[i][1][d+1] = max(dp[i][1][d+1], dp[i-1][0][d] + 1) 解释：修复后当前 ')' 变为 '('，因此深度变为1。 情况3 ：即使有左括号，也可主动失配（d < k），将 ')' 修复为 '('，深度增1： dp[i][j+1][d+1] = max(dp[i][j+1][d+1], dp[i-1][j][d] + 1) 初始化 dp[0][0][0] = 0 ，其余初始为负无穷（表示不可达）。 最终答案 所有 dp[n][0][d] （0 ≤ d ≤ k）的最大值，因为最终要求所有左括号被匹配（深度为0）。 复杂度分析 时间复杂度：O(n²k)，其中 n 为字符串长度，j 的范围不超过 n。 空间复杂度：可通过滚动数组优化至 O(nk)。 示例 以 s = "())" ， k = 1 为例： 最优子序列为 "()" （选第1、2字符），无失配，长度为2。 若选全部3字符，可通过修复第3个 ')' 为 '('，得到 "()(" （深度1），但深度非0，无效。 最终答案为2。 通过以上步骤，可逐步计算所有状态，找到最长有效括号子序列。