线性动态规划：最长有效括号匹配子序列的变种——允许一次失配的最长有效括号子序列 题目描述 给你一个由 '(' 和 ')' 组成的字符串 s。我们需要找出最长的有效括号子序列的长度。这个子序列不要求是连续的，但必须满足有效的括号匹配规则。不过，在这个变种问题中，我们被允许在匹配过程中出现一次“失配”。一次失配定义为：可以选择子序列中的某一个字符，将其视为它的对立括号（即 '(' 可视为 ')'，或 ')' 可视为 '('）来帮助完成匹配。 例如，对于字符串 s = "())": 如果不允许失配，最长有效括号子序列是 "()"，长度为2。 如果允许一次失配，我们可以将最后一个 ')' 视为 '('，但这样无法形成匹配。实际上，整个序列 "())" 本身，如果我们把中间的 ')' 视为 '('，那么它和最后一个 ')' 能形成一对（视为后的序列像 "()"），但第一个 '(' 没有匹配。更优的做法是：取第一个 '(' 和最后一个 ')'，它们自然匹配，长度为2。或者，取所有三个字符，将中间的 ')' 视为 '('，那么序列变为（视作）"(()"，这仍然不是有效的。所以我们需要一个系统的解法。 更清晰的例子：s = "()())" 无失配：最长有效子序列可以是 "()()"，长度为4。 允许一次失配：我们可以考虑将某个字符翻转。例如，如果我们取整个字符串，并将第三个字符 '(' 翻转成 ')'，那么序列变为（视作）"())()"，这仍然无效。但如果我们取索引0,1,3,4的字符 "()()"，它本身已经有效，长度为4，不需要使用失配。所以答案仍是4。 再一个例子：s = "((())" 无失配：最长有效子序列是 "(())"，长度为4。 允许一次失配：我们可以取整个字符串，将第一个字符 '(' 翻转成 ')'。那么序列变为（视作）")(())"，这仍然无效。但如果我们取索引1,2,3,4的字符 "(())"，长度为4。如果我们尝试使用失配，比如取所有字符，将第一个字符翻转，希望能和最后一个字符匹配？但这样中间部分会失配。实际上，这个问题比寻找连续子串的版本更复杂，因为它涉及子序列和一次翻转机会。 解题过程 我们将使用动态规划来解决这个问题。定义状态是解决动态规划问题的关键。 定义状态 我们定义一个二维动态规划数组 dp[i][j][k] ： i : 表示当前考虑字符串 s 的子串 s[ 0..i ]（包含i）。 j : 表示当前子序列中，尚未匹配的 '(' 的数量（可以理解为开括号的盈余）。 k : 表示我们是否已经使用了那一次“翻转”字符的权利。k=0 表示尚未使用，k=1 表示已经使用了一次翻转。 dp[i][j][k] 的值表示：在字符串 s 的前 i 个字符构成的子串中，找到一个括号子序列，使得在允许最多 k 次翻转的情况下，处理完这个子序列后，开括号的盈余为 j，此时该有效子序列的最大长度是多少？ 注意 ：这里的“长度”是指我们选择的这个子序列中，有多少个字符 被匹配成功了 。一个成功的匹配需要一对括号（无论是自然匹配还是通过翻转实现匹配）都贡献长度2。但是，我们的状态定义方式可以巧妙地记录这个信息。 实际上，更精确和常见的做法是定义 dp[i][j][k] 为：考虑前i个字符，当前开括号盈余为j，是否使用过翻转(k=0/1)的情况下，所能形成的 有效括号对的数量 （即匹配成功的括号对数乘以2）。但这样最终答案需要乘以2。另一种等价且更直观的思路是：我们的状态值直接记录有效长度（即匹配成功的字符数）。 然而，为了更清晰地处理“翻转”操作，我们采用一种基于“平衡度”和“决策”的DP。我们让 dp[i][j][k] 表示考虑前i个字符，当前平衡度为j（即'('个数减去')'个数），使用翻转次数为k（0或1）时，所能选择的最长子序列的长度。注意，这个子序列必须是有效的，所以最终j应该为0，并且在过程中j不能为负（因为如果j为负，意味着有未匹配的')'，这在常规有效括号序列中是不允许的，但翻转操作可能会改变这一约束？我们需要仔细思考）。 由于允许一次翻转，规则变得复杂。一个更稳健的方法是采用两种状态分别表示常规匹配和翻转匹配的思想，但这样状态会非常复杂。 我们换一种思路，使用一个经典的解决带一次错误/修改的最长有效括号子序列的方法： 状态定义 ： 我们定义 dp[i][j] ，其中： i 表示当前处理到字符串的第 i 个字符（从0开始）。 j 表示当前的平衡度（即 '(' 的数量减去 ')' 的数量）。 但是为了记录是否使用过翻转，我们需要增加一维。然而，有一个技巧：我们可以将问题转化为寻找两个不同的最长有效括号子序列路径，一个路径是完全没有错误的，另一个路径是允许出现一次错误的。这个“错误”可以发生在任何时候。 一个经典的解决方案（适用于允许一次失配的最长有效括号子序列）是使用两个DP数组： correct[i][j] : 表示考虑 s[ 0..i] 的子序列，平衡度为 j，并且 没有使用过翻转 的情况下，最长的有效子序列长度。 flipped[i][j] : 表示考虑 s[ 0..i] 的子序列，平衡度为 j，并且 已经使用过一次翻转 的情况下，最长的有效子序列长度。 状态转移方程 ： 对于每个字符 s[ i ]（假设索引从0开始），我们有两种选择：选择这个字符加入子序列，或者不选。 如果我们选择不选这个字符，状态直接继承： correct[i][j] 可以从 correct[i-1][j] 继承。 flipped[i][j] 可以从 flipped[i-1][j] 继承。 如果我们选择加入这个字符，那么我们需要考虑这个字符原本是什么，以及我们是否要翻转它。注意，翻转操作只有在对应状态下允许时才能使用。 我们分情况讨论： 情况A：处理 correct 数组（尚未使用翻转） 字符 s[ i ] 有两种可能：'(' 或 ')'。 s[ i] 是 '(' : 如果我们不翻转它，我们将其视为 '('，那么平衡度 j 会增加1。所以状态转移为： correct[i][j] = max(correct[i][j], correct[i-1][j-1] + 1) （注意：这里+1是因为我们加入了一个字符，但这个字符是开括号，尚未形成匹配对，所以只是增加长度1和平衡度1。然而，在最终的有效序列中，这个开括号必须被匹配掉才算有效长度。所以更准确的做法是记录匹配成功的括号对数量？） 我们发现直接记录长度会遇到问题：一个单独的 '(' 或 ')' 如果最终没有被匹配，它不应该被计入有效长度。所以我们的状态值应该只记录 已经匹配成功的字符数量 。 重新思考并精确定义状态 让我们重新定义，这是解决这个问题的关键： 定义 dp[i][j][k] 为：考虑字符串 s 的前 i 个字符，当前平衡度为 j（j>=0），并且已经使用了 k 次翻转（k=0或1）的情况下，所能形成的 有效括号子序列的最大长度（即匹配成功的字符数） 。 重要 ：平衡度 j 必须始终 >= 0。当我们加入一个字符（无论是原意还是翻转后），如果导致 j < 0，那么这个选择是无效的，不能转移。 现在，对于每个位置 i，每个可能的平衡度 j，每个翻转标志 k，我们考虑两种决策：跳过 s[ i] 或者 选择 s[ i ]。 决策1：跳过 s[ i] dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]) 决策2：选择 s[ i] 当我们选择 s[ i] 时，我们可以选择以它的原始含义使用，或者翻转它（如果 k 还允许翻转，即 k_ prev = k 如果本次不翻转，或者 k_ prev = k-1 如果本次翻转且 k>0）。 具体有四种子情况： a. 不使用翻转，s[ i ] 作为本身： - 如果 s[ i ] == '(': 那么它相当于一个开括号，平衡度会变成 j+1。但是，这个开括号还没有被匹配，所以它暂时不能贡献有效的“匹配长度”。然而，我们的状态 dp 记录的是已经匹配的长度。当我们加入一个 '('，它只是增加了未匹配的开括号数量，并没有形成新的匹配对，所以有效长度不应该增加？这似乎不对。 我们需要再次修正：我们的状态 dp 记录的是 当前子序列的总长度 ，这个总长度包括已经匹配的字符和尚未匹配的字符（即开括号）。因为最终只要 j=0，整个序列就是有效的。所以当我们加入一个字符，只要操作后平衡度 j>=0，我们就可以把该字符计入长度。 所以新的定义： dp[i][j][k] 表示考虑前i个字符，当前平衡度为j（j>=0），已使用翻转次数为k的情况下，所选子序列的最大长度（即子序列中字符的个数）。这个子序列必须满足：在允许最多k次翻转的条件下，它是一个有效的括号序列（即最终j=0，且每一步j>=0）。但注意，我们计算的是整个子序列的长度，而不仅仅是匹配成功的部分。 这样定义后，状态转移就清晰了： 跳过 s[ i]: dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]) 选择 s[ i ]，并决定是否翻转： 我们考虑这个字符被加入后的实际效果（是作为 '(' 还是作为 ')'）: 设 char_effect 表示这个字符最终起的作用：1 表示它是 '('（会增加平衡度j），-1 表示它是 ')'（会减少平衡度j）。 那么，新的平衡度 j_new = j + char_effect 。 选择这个字符的条件是 j_new >= 0 。 长度会增加1。 现在分情况： 情况1：不翻转。那么 char_effect 由 s[ i] 本身决定：s[ i]=='(‘ -> 1; s[ i ]==’)’ -> -1。 情况2：翻转（前提是 k>=1）。那么 char_effect 与 s[ i] 本身相反：s[ i]=='(‘ -> -1; s[ i ]==’)’ -> 1。 然后进行状态转移： dp[i][j_new][k_used] = max( dp[i][j_new][k_used], dp[i-1][j][k_prev] + 1 ) 其中： 如果不翻转： k_used = k_prev = k 。 如果翻转： k_used = k , k_prev = k - 1 （因为本次翻转消耗了一次机会）。 初始化 ： dp[0][0][0] = 0 （考虑前0个字符，平衡度0，未翻转，长度为0） 其他状态初始化为负无穷（-inf），表示不可达。 最终答案 ： 我们最终需要的是一个平衡度为0的有效序列。所以答案是所有 i 处理完后， dp[n][0][k] 的最大值，其中 k=0 或 1。即 max( dp[n][0][0], dp[n][0][1] ) 。 遍历顺序 ： i 从 0 到 n-1 遍历。 对于每个 i，遍历所有可能的平衡度 j (从0到某个上界，上界最大为n，因为最多有n个'(')。 对于每个 j, k，进行状态转移。 举例说明 以 s = "())" 为例，n=3。 初始化：dp[ 0][ 0][ 0 ] = 0。 i=0, s[ 0 ] = '(': 跳过: dp[ 1][ 0][ 0] = max(..., dp[ 0][ 0][ 0 ]=0) -> 0。 选择，不翻转：char_ effect=1, j_ new=0+1=1, k不变=0。 dp[ 1][ 1][ 0 ] = max(..., 0+1=1)。 选择，翻转（k_ prev=0, k_ used=1）：char_ effect=-1, j_ new=0-1=-1 -> 无效（j_ new <0），不转移。 i=1, s[ 1 ] = ')': 对于状态 (j=0, k=0): 跳过: 继承 dp[ 1][ 0][ 0 ]=0。 选择，不翻转: char_ effect=-1, j_ new=0-1=-1 无效。 选择，翻转: k_ prev=0-1? 不行，因为k_ prev需要>=0。实际上，k_ prev应该是翻转前的k，即0。翻转消耗一次，k_ used=1。char_ effect=1（因为')'翻转为'('），j_ new=0+1=1。所以 dp[ 2][ 1][ 1 ] = max(..., 0+1=1)。 对于状态 (j=1, k=0): 跳过: 继承 dp[ 1][ 1][ 0 ]=1。 选择，不翻转: char_ effect=-1, j_ new=1-1=0。 dp[ 2][ 0][ 0 ] = max(..., 1+1=2)。 选择，翻转: k_ prev=0, k_ used=1, char_ effect=1, j_ new=1+1=2。 dp[ 2][ 2][ 1 ] = max(..., 1+1=2)。 i=2, s[ 2 ] = ')': 状态 (j=0, k=0): 已有值2。 跳过: 继承2。 选择，不翻转: char_ effect=-1, j_ new=0-1=-1 无效。 选择，翻转: k_ prev=0, k_ used=1, char_ effect=1, j_ new=0+1=1。 dp[ 3][ 1][ 1 ] = max(..., 2+1=3)。 状态 (j=0, k=1): 尚无值。 状态 (j=1, k=1): 值=1。 跳过: 继承1。 选择，不翻转: char_ effect=-1, j_ new=1-1=0。 dp[ 3][ 0][ 1 ] = max(..., 1+1=2)。 选择，翻转: k_ prev=1-1=0? 不对，当前k=1，翻转需要从k_ prev=0的状态转移。但我们的状态是 (j=1, k=1) 的 k_ prev 应该是0吗？不，当我们考虑“选择并翻转”时，我们是从一个“尚未使用这次翻转”的状态转移过来的。所以对于当前状态 (j=1, k=1)，如果我们想再翻转一次，是不允许的，因为k=1已经用掉了翻转机会。所以只能从 k_ prev=1 的状态尝试“不翻转”的选择，或者从 k_ prev=0 的状态尝试“翻转”的选择。但“翻转”选择会消耗一次机会，所以只能从 k_ prev=0 的状态来。所以我们这里需要检查：对于“翻转”选择，我们要求 k_ prev = k_ used - 1。所以如果当前想得到 k_ used=1，那么 k_ prev 必须是0。所以对于状态 (j=1, k=1) 本身，它不能作为“翻转”选择的源，因为它的k_ prev是1，不等于0。我们需要遍历所有可能的前驱状态。 正确的做法是：在计算 dp[ i][ j_ new][ k_ used] 时，我们考虑前一个状态 (i-1, j, k_ prev)： - 对于“不翻转”选择：k_ prev = k_ used。 - 对于“翻转”选择：k_ prev = k_ used - 1。 所以对于 i=2, s[ 2]=')'，我们计算状态 (j_ new=1, k_ used=1) 时，可以通过“翻转”选择，从 i=1 的 (j=0, k_ prev=0) 转移过来：dp[ 1][ 0][ 0]=0，然后选择并翻转 s[ 2]，char_ effect=1, j_ new=0+1=1, 长度=0+1=1。但之前我们已经从其他路径得到了 dp[ 2][ 1][ 1 ]=1，所以这里可能不是最大。 最终，在 i=3 时，我们看平衡度 j=0 的状态： dp[ 3][ 0][ 0] = 2 （来自路径：选择s[ 0]和s[ 1 ]，不翻转） dp[ 3][ 0][ 1] = 2 （来自路径：例如选择s[ 0]和s[ 2]，并对s[ 2]进行翻转？但需要检查平衡度：选择s[ 0]('(') -> j=1, k=0; 选择s 2 ')并翻转为'(' -> j=1+1=2, k=1? 不对，这样最终j=2不为0。所以上面计算 dp[ 3][ 0][ 1]=2 的路径是：从状态 (j=1, k=1) 在 i=2 时选择不翻转 s[ 2]（作为')'），j_ new=1-1=0，长度=1+1=2。而 (j=1,k=1) 状态是在 i=1 时，从 (j=0,k=0) 选择翻转 s[ 1 ] 得到的。 所以最大长度是 max(2, 2) = 2。对于字符串 "())"，允许一次失配的最长有效括号子序列长度也是2（例如 "()"）。 这个动态规划方法通过状态 (i, j, k) 清晰地刻画了问题，并通过遍历所有决策（跳过/选择且翻转/选择不翻转）来逐步构建最优解。虽然状态转移需要考虑的情况较多，但通过合理的定义和遍历，可以系统地解决这个问题。