线性动态规划：最长有效括号匹配子序列的变种——允许最多k次失配的最长有效括号子序列 题目描述 给定一个由 '(' 和 ')' 组成的字符串 s，以及一个非负整数 k。我们需要找到一个最长的子序列（不要求连续），使得这个子序列是有效的括号序列，但允许最多 k 次失配。这里的失配指的是：在子序列中，某个位置的括号无法找到与之匹配的括号（例如，多余的右括号或左括号）。注意，子序列是通过删除原字符串中的某些字符（也可以不删除）得到的序列。 解题过程 1. 问题分析 这是一个带有容错机制的最长有效括号子序列问题。与标准问题不同，我们允许子序列中存在最多 k 个未匹配的括号。我们需要设计一个动态规划状态来记录当前未匹配的括号数量。 2. 状态定义 定义 dp[ i][ j][ m ] 表示考虑字符串 s 的前 i 个字符，子序列中当前未匹配的左括号数量为 j，并且已经使用了 m 次失配机会时，所能得到的最长有效括号子序列的长度。 i：考虑前 i 个字符（0 ≤ i ≤ n） j：当前未匹配的左括号数量（0 ≤ j ≤ n） m：已使用的失配次数（0 ≤ m ≤ k） 3. 状态转移 对于每个字符 s[ i ]（索引从1开始），我们有两种选择： 不选 s[ i]：状态直接继承，即 dp[ i][ j][ m] = dp[ i-1][ j][ m ] 选 s[ i ]： 如果 s[ i ] 是 '('： 我们可以将其视为一个未匹配的左括号，此时 j 增加1，m 不变：dp[ i][ j][ m] = max(dp[ i][ j][ m], dp[ i-1][ j-1][ m ] + 1) 或者我们将其视为一次失配（即不匹配的左括号），此时 j 不变，m 增加1（如果 m < k）：dp[ i][ j][ m] = max(dp[ i][ j][ m], dp[ i-1][ j][ m-1 ] + 1) 如果 s[ i ] 是 ')'： 如果 j > 0，我们可以匹配一个左括号，此时 j 减少1，m 不变：dp[ i][ j][ m] = max(dp[ i][ j][ m], dp[ i-1][ j+1][ m ] + 1) 或者我们将其视为一次失配（即不匹配的右括号），此时 j 不变，m 增加1（如果 m < k）：dp[ i][ j][ m] = max(dp[ i][ j][ m], dp[ i-1][ j][ m-1 ] + 1) 4. 初始化 dp[ 0][ 0][ 0 ] = 0，表示没有字符时，未匹配括号数为0，失配次数为0，长度为0。 其他状态初始化为负无穷（表示不可达）。 5. 最终答案 答案为所有 dp[ n][ 0][ m ]（0 ≤ m ≤ k）中的最大值，表示最终未匹配括号数为0（即所有括号都匹配或作为失配处理），且失配次数不超过 k 的最长子序列长度。 6. 复杂度优化 状态数为 O(n²k)，可以通过滚动数组优化空间复杂度至 O(nk)。