线性动态规划：最长有效括号匹配子序列的变种——允许最多k次失配的最长有效括号子序列（进阶版：失配位置可修复） 题目描述 给定一个由 '(' 和 ')' 组成的字符串 s ，以及一个整数 k （ k ≥ 0 ）。定义“有效括号子序列”为：通过删除 s 中的若干字符（可以不删除）后，剩余字符构成的序列是有效的括号序列（即每个左括号都能找到对应的右括号匹配，且整体顺序正确）。但允许子序列中最多存在 k 个“失配”位置（即原本无法匹配的括号），且每个失配位置可以通过一次“修复”操作（如翻转括号方向）变为匹配。求修复后可能的最长有效括号子序列的长度。 关键点 子序列不要求连续，但需保持原顺序。 允许修复失配位置，修复后该位置视为匹配。 目标是最长子序列长度，而非连续子串。 解题思路 使用动态规划，定义状态 dp[i][j][d] ： i ：考虑字符串 s 的前 i 个字符。 j ：当前未匹配的左括号数量（即栈深度）。 d ：已使用的修复次数（ 0 ≤ d ≤ k ）。 状态值表示在修复不超过 d 次的情况下，前 i 个字符形成的子序列中，未匹配左括号为 j 时的最大长度。 状态转移 对每个字符 s[i] （索引从1开始），有两种选择： 不选当前字符 ：状态直接继承： dp[i][j][d] = dp[i-1][j][d] 。 选当前字符 ：根据字符是 '(' 或 ')' 处理： 若 s[i] == '(' ： 不修复：作为左括号，未匹配左括号数 j 增加1，长度+1： dp[i][j][d] = max(dp[i][j][d], dp[i-1][j-1][d] + 1) 。 修复为 ')' （需 d < k ）：作为右括号，若 j ≥ 1 则匹配一个左括号， j 减1，长度+1： dp[i][j][d] = max(dp[i][j][d], dp[i-1][j+1][d+1] + 1) 。 若 s[i] == ')' ： 不修复：作为右括号，若 j ≥ 1 则匹配左括号， j 减1，长度+1： dp[i][j][d] = max(dp[i][j][d], dp[i-1][j+1][d] + 1) 。 修复为 '(' （需 d < k ）：作为左括号， j 增加1，长度+1： dp[i][j][d] = max(dp[i][j][d], dp[i-1][j-1][d+1] + 1) 。 初始化和边界 初始状态： dp[0][0][0] = 0 ，其余为负无穷（表示不可达）。 j 的范围： 0 ≤ j ≤ n （n为字符串长度），因为未匹配左括号数不会超过总字符数。 最终答案 所有 dp[n][0][d] （ 0 ≤ d ≤ k ）中的最大值，表示所有字符处理完后无未匹配左括号且修复次数不超过 k 的最长子序列长度。 复杂度分析 时间复杂度：O(n² × k)，其中 n 为字符串长度。 空间复杂度：可优化至 O(n × k) 使用滚动数组。 示例 设 s = "())" , k = 1 ： 最优解：选全部字符，修复最后一个 ')' 为 '(' ，得到 "()(" （修复后深度为1，但允许最后未匹配？需注意：最终需 j=0 ）。实际应选前两个字符 "()" ，长度2。 通过DP表逐步计算可得最大长度为2。