线性动态规划：最长有效括号匹配子串的变种——允许最多k次失配的最长有效括号子串
我将为您讲解一个线性动态规划问题：在允许最多k次失配的情况下，找到最长的有效括号子串。
问题描述
给定一个只包含'('和')'的字符串s，以及一个非负整数k。我们需要找到最长的连续子串，使得在最多修改k个字符（将'('改为')'或将')'改为'('）后，该子串能成为有效的括号序列。
有效括号序列定义为：
- 空字符串是有效的
- 如果A是有效的，那么(A)也是有效的
- 如果A和B都是有效的，那么AB也是有效的
解题思路
步骤1：理解问题本质
这个问题是经典最长有效括号问题的扩展。在经典问题中，我们要求子串本身就是有效的括号序列，而这里允许最多k次修改。
关键观察：
- 有效括号序列中，左括号和右括号数量相等
- 在任何前缀中，左括号数量不少于右括号数量
- 修改一个字符相当于改变括号的平衡性
步骤2：定义状态
我们使用动态规划来解决这个问题。定义状态：
dp[i][j]表示以第i个字符结尾，净修改次数为j时的最大长度
其中：
- i 表示字符串的索引（0 ≤ i < n）
- j 表示净修改次数（0 ≤ j ≤ k）
- 净修改次数指的是左括号改为右括号的次数减去右括号改为左括号的次数
步骤3：状态转移方程
对于每个位置i和每个可能的修改次数j：
-
如果s[i]是'('：
- 不修改：
dp[i][j] = dp[i-1][j] + 1（如果j ≥ 0） - 修改为')'：
dp[i][j] = dp[i-1][j-1] + 1（如果j > 0）
- 不修改：
-
如果s[i]是')'：
- 不修改：
dp[i][j] = dp[i-1][j] + 1（如果j ≥ 0） - 修改为'('：
dp[i][j] = dp[i-1][j+1] + 1（如果j < k）
- 不修改：
但这里有个问题：我们需要确保修改后的序列是有效的。因此需要引入平衡性的概念。
步骤4：改进的状态定义
我们重新定义状态：
dp[i][balance][changes] 表示考虑前i个字符，当前平衡度为balance，已使用changes次修改时的最长有效长度。
其中：
- balance：左括号数量减去右括号数量
- changes：已使用的修改次数（0 ≤ changes ≤ k）
状态转移：
对于每个位置i，对于所有可能的balance和changes：
如果s[i]是'('：
-
不修改：新的balance = balance + 1
- 如果balance ≥ 0：
dp[i][balance+1][changes] = max(dp[i][balance+1][changes], dp[i-1][balance][changes] + 1)
- 如果balance ≥ 0：
-
修改为')'：新的balance = balance - 1，新的changes = changes + 1
- 如果changes < k 且 balance ≥ 1：
dp[i][balance-1][changes+1] = max(dp[i][balance-1][changes+1], dp[i-1][balance][changes] + 1)
- 如果changes < k 且 balance ≥ 1：
如果s[i]是')'：
-
不修改：新的balance = balance - 1
- 如果balance ≥ 1：
dp[i][balance-1][changes] = max(dp[i][balance-1][changes], dp[i-1][balance][changes] + 1)
- 如果balance ≥ 1：
-
修改为'('：新的balance = balance + 1，新的changes = changes + 1
- 如果changes < k：
dp[i][balance+1][changes+1] = max(dp[i][balance+1][changes+1], dp[i-1][balance][changes] + 1)
- 如果changes < k：
步骤5：初始化和边界条件
dp[0][0][0] = 0- 其他状态初始化为-∞（表示不可达）
- 对于任何状态，balance不能为负（因为这意味着右括号多于左括号）
步骤6：答案提取
最终答案是所有dp[i][0][changes]中的最大值，其中0 ≤ i < n，0 ≤ changes ≤ k。
详细示例
考虑字符串s = "())"，k = 1
初始化：dp[0][0][0] = 0
i=0, s[0]='('：
- 不修改：dp[0][1][0] = 1
- 修改：dp[0][-1][1] = 1（但balance为负，无效）
i=1, s[1]=')'：
从状态(1,0)：
- 不修改：dp[1][0][0] = max(dp[1][0][0], 2) = 2
从状态(1,1)： - 修改：dp[1][2][2] = 2（但changes > k，不考虑）
i=2, s[2]=')'：
从状态(0,0)：
- 不修改：dp[2][-1][0]（无效）
- 修改：dp[2][1][1] = 3
最终答案：max(2, 3) = 3
复杂度分析
- 时间复杂度：O(n² × k)，其中n是字符串长度
- 空间复杂度：O(n × k)，可以通过滚动数组优化到O(k)
这个算法通过动态规划巧妙地处理了括号平衡性和修改次数的约束，找到了在允许有限次修改情况下的最长有效括号子串。