线性动态规划：最少操作使字符串平衡（Minimum Operations to Balance a String）
字数 5122 2025-12-12 05:02:20

线性动态规划：最少操作使字符串平衡（Minimum Operations to Balance a String）

题目描述

给定一个长度为 \(n\) 的只包含字符 '(' 和 ')' 的字符串 s。定义一次操作：你可以将字符串中的任意位置的字符替换成另一个字符（即 '(' 变 ')' 或 ')' 变 '('）。你的目标是让字符串平衡。

平衡字符串的定义：

  1. 字符串中 '(' 和 ')' 的数量相等。
  2. 对于字符串的每一个前缀（从开头到任意位置的子串），其中 '(' 的数量必须大于等于 ')' 的数量（即前缀中不会出现 ')' 比 '(' 多的情况，也就是经典的有效括号前缀条件）。

请你计算，最少需要多少次替换操作，才能将字符串 s 变成平衡字符串。

示例 1：

输入：s = "())("
输出：1
解释：将最后一个字符 '(' 替换为 ')'，得到 "())" -> "()" 这样的平衡？不对，我们先检查：
原串：())(
操作：将 s[3]='(' 替换为 ')'，得到 "()))" -> 这并不满足前缀条件。
实际上，最少操作是替换 s[2]=')' 为 '('，得到 "(()("，仍然不对。
正确操作：将 s[0]='(' 保持不变，s[1]=')' 替换为 '('，得到 "((()" 也不对。
让我们仔细分析。

我们先明确：题目要求最终字符串满足两个条件：数量相等 + 前缀中左括号不少于右括号。
注意：操作是替换，不是插入或删除。所以最终字符串长度不变，只是部分字符改变了。

我们从头思考。

逐步分析

第一步：理解平衡条件

对于一个最终平衡的字符串：

  1. 长度 n 必须是偶数，因为左右括号数量相等。
  2. 设最终字符串有 \(n/2\) 个 '(' 和 \(n/2\) 个 ')'。
  3. 前缀条件：对于任何位置 \(i\)（1 ≤ i ≤ n），前缀中 '(' 的数量 ≥ ')' 的数量。

这其实就是经典的有效括号序列的前缀条件，并且最终整个字符串的左右括号数相等。

第二步：问题转化

我们只能通过替换字符来改变字符串，不能改变长度。
设最终字符串中 '(' 的数量为 \(n/2\)，')' 的数量为 \(n/2\)。

初始字符串中，'(' 的数量记为 leftCount，')' 的数量为 rightCount。

如果我们直接强行让最终有 \(n/2\) 个 '('，那么需要：

  • 如果原串中 '(' 少于 \(n/2\)，则少几个 '(' 就要把几个 ')' 改为 '('。
  • 如果原串中 '(' 多于 \(n/2\)，则多几个 '(' 就要把几个 '(' 改为 ')'。

这样修改后，数量条件就满足了。但修改后的字符串不一定满足前缀条件。
所以，我们需要在满足前缀条件的前提下，尽量少替换。

第三步：动态规划状态设计

我们可以从左到右扫描字符串，记录当前前缀中 '(' 的数量与 ')' 的数量的差值（称为平衡度 balance），必须保持 balance ≥ 0。

同时，我们还要记录已经放置了多少个 '('（因为最终必须有 \(n/2\) 个 '('）。

定义状态：
\(dp[i][j][b]\) 表示考虑前 i 个字符，已经放置了 j 个 '('（这 j 个 '(' 可能是原串的 '(' 没改，或者原串是 ')' 改成的 '('），并且当前平衡度 balance = b（即 '(' 比 ')' 多 b 个）的情况下，最少的替换操作次数。

但是这样状态维度高：i 最多 n，j 最多 n，b 最多 n。复杂度 O(n^3)，可能较大。我们需要优化。

第四步：优化状态设计

注意到最终必须有 \(n/2\) 个 '('，所以 j 其实由最终目标固定了一半。但我们在扫描过程中可以决定每个位置是放 '(' 还是 ')'，只要最终 j = n/2 且 balance 始终 ≥0，且 balance 最终为 0。

更常见的思路：贪心 + 动态规划。
有一个经典问题与此类似：给定初始括号串，可以翻转（即替换）括号，求最少的翻转次数使之成为有效括号序列。
解法：先确保最终左右括号数量均为 n/2，然后扫描决定哪些位置必须改为 '('，哪些必须改为 ')'。

让我们直接推导递推关系。

设最终字符串为 t，满足：

  1. t 有 n/2 个 '('，n/2 个 ')'。
  2. 对于所有前缀，'(' 数量 ≥ ')' 数量。

定义 cost(i, ch) 为将 s[i] 改为字符 ch 的代价：若 s[i] == ch 则代价 0，否则代价 1（因为一次替换）。

我们按顺序决定 t[i] 是 '(' 还是 ')'。
设 f(i, open, bal) 为考虑前 i 个字符，已经用了 open 个 '('，当前平衡度 bal = (open - close) = bal（即 '(' 比 ')' 多 bal 个）的最小代价。
其中 close = i - open 是已用的 ')' 数量，bal = open - close = 2*open - i。

限制：

  • bal ≥ 0（前缀条件）。
  • open ≤ n/2（不能超过最终 '(' 数量）。
  • i - open ≤ n/2（不能超过最终 ')' 数量，即 close ≤ n/2）。

目标：f(n, n/2, 0)。

转移：
对于第 i 个位置（0-index），我们可以放 '(' 或 ')'。

如果放 '('：
前提是 open+1 ≤ n/2，且新的 bal' = bal+1 ≥ 0（自动满足，因为 bal≥0 时 bal+1>0）。
代价 = cost(i, '(')。

如果放 ')'：
前提是 i - (open+1) ≤ n/2？不对，放 ')' 时 open 不变，close+1，所以需要 close+1 ≤ n/2，即 i+1 - open ≤ n/2。
并且新的 bal' = bal-1 ≥ 0。
代价 = cost(i, ')')。

因此：

f(i, open, bal) = min(
    f(i-1, open-1, bal-1) + cost(i, '(')   if open>0 and bal-1≥0,
    f(i-1, open, bal+1) + cost(i, ')')     if (i-open) ≤ n/2 and bal+1 ≥0? 注意这里 bal 是上一步的 bal，现在放 ')' 则新 bal = 上一步 bal -1，所以需要上一步 bal-1≥0。
)

小心下标的处理。我们详细展开。

第五步：简化状态与迭代实现

我们可以减少一维，注意到 bal = 2*open - i，所以如果我们知道 i 和 open，bal 就确定了。
因此状态可以设为 f(i, open)，表示前 i 个字符中放了 open 个 '(' 的最小代价，并且中间过程 bal 始终 ≥0。

转移：
对于 i 从 1 到 n：

  • 如果我们让 t[i] = '('，需要 open > 0（因为 open 是计数已放 '(' 数，但这里 open 表示前 i 个中 '(' 的总数，所以在放 '(' 时，新的 open' = open，对应上一步的 open-1 个 '('）。我们来精确推导：

设当前考虑完第 i 个字符，共有 open 个 '('。那么第 i 个字符有两种可能：

  1. 第 i 个字符是 '('：那么前 i-1 个字符中应有 open-1 个 '('，且那时平衡度 bal_{i-1} = (open-1) - (i-1 - (open-1)) = 2*(open-1) - (i-1) = 2open - i - 1。
    这个值必须 ≥0（前缀条件在第 i-1 步时）。
    转移到 f(i, open) = f(i-1, open-1) + cost(i, '(')，前提是 open≥1 且 2    open - i - 1 ≥ 0。

  2. 第 i 个字符是 ')'：那么前 i-1 个字符中应有 open 个 '('，且那时平衡度 bal_{i-1} = 2open - (i-1)。
    现在在第 i 步放 ')'，新平衡度 bal_i = 2    open - i，必须 ≥0。
    所以需要 2open - i ≥ 0。
    转移到 f(i, open) = f(i-1, open) + cost(i, ')')，前提是 open ≤ i 且 2    open - i ≥ 0。

初始：
f(0, 0) = 0，其余无穷大。

目标：
f(n, n/2)，前提是 n 为偶数（否则不可能平衡）。

第六步：边界与答案

最终答案就是 f(n, n/2)，其中 n 必须是偶数，否则返回 -1 或不可能。

复杂度 O(n^2)，但 n 可以较大，不过这个状态数 1000*1000 可能较大。我们可以优化，注意到 open 的取值范围受前缀条件限制，所以很多状态不可达。但作为通用解法，我们实现时可以只计算可达状态。

第七步：示例推演

例：s = "())("，n=4 偶数。

目标 open=2。

i=1（字符 s[0]='('）：

  • 放 '('：open=1，需要 2*1 - 1 - 1 = 0 ≥ 0，代价 0，f(1,1)=0。
  • 放 ')'：open=0，需要 2*0 - 1 = -1 <0，不允许。
    其余 open 值无穷。

i=2（字符 s[1]=')'）：
open 从 0..2。
open=1：可以从 f(1,1) 放 ')' 得到：需要 21 - 2 = 0 ≥ 0，代价 1，f(2,1)=1。
或者从 f(1,0) 放 '('，但 f(1,0) 不存在。
open=2：可以从 f(1,1) 放 '('：需要 22 - 2 - 1 = 1 ≥ 0，代价 0，f(2,2)=0。

i=3（字符 s[2]=')'）：
open=1：从 f(2,1) 放 ')'：21 - 3 = -1 <0 不允许。从 f(2,0) 放 '(' 不存在。
open=2：从 f(2,2) 放 ')'：22 - 3 = 1 ≥0，代价 1，f(3,2)=1。
从 f(2,1) 放 '('：需要 open≥1 且 22 - 3 -1 = 0≥0，代价 1，得 f(3,2)=min(1, 1+1)=1。
open=3：从 f(2,2) 放 '('：需要 23 - 3 -1 = 2≥0，代价 0，f(3,3)=0。

i=4（字符 s[3]='('）：
目标 open=2。
open=2：从 f(3,2) 放 ')'：需要 22 - 4 = 0≥0，代价 0（因为 s[3]='(' 要变成 ')' 代价 1？不对，这里 cost(4, ')') 是 s[3] 改为 ')' 的代价，原 s[3]='('，所以代价 1），所以 f(4,2)=1+1=2。
从 f(3,1) 放 '('：f(3,1) 不存在。
open=3：从 f(3,3) 放 ')'：需要 23 - 4 = 2≥0，代价 1，f(4,3)=0+1=1。
从 f(3,2) 放 '('：需要 23 - 4 -1 = 1≥0，代价 0，f(4,3)=min(1, 1+0)=1。
open=4：从 f(3,3) 放 '('：需要 24 - 4 -1 = 3≥0，代价 0，f(4,4)=0。

最终 f(4,2)=2？但前面我们手工算似乎 1 次操作就行？检查：s="())("
一种改法：s[2]=')' 改为 '('，得到 "(()("，现在：'(' 数量 3，')' 数量 1，不符合数量相等（需要 2 和 2）。还要再改一个 '(' 为 ')'，比如 s[3]='(' 改为 ')'，得到 "(())"，这个串平衡吗？前缀：'(' 数量始终 ≥')' 数量，且最终各 2 个，平衡。操作次数 2。
另一种：s[0]='(' 改为 ')'，得到 ")))("，不行。
似乎最少就是 2 次。但我之前以为 1 次可能，验证不行。所以我们的 dp 结果 f(4,2)=2 是对的。

因此示例答案应该是 2，不是之前示例给的 1（原题示例可能给错，或者是不同变种）。

最终算法步骤

  1. 如果 n 是奇数，返回 -1（不可能平衡）。
  2. 初始化 dp 数组，dp[0][0] = 0，其他为无穷大。
  3. 遍历 i = 1 到 n：
    • 遍历可能的 open 数（从 0 到 i）：
      a. 如果 open ≥ 1 且 2open - i - 1 ≥ 0，则 dp[i][open] = min(dp[i][open], dp[i-1][open-1] + (s[i-1] != '('))。
      b. 如果 2      open - i ≥ 0，则 dp[i][open] = min(dp[i][open], dp[i-1][open] + (s[i-1] != ')')).
  4. 答案为 dp[n][n/2]。

这样我们就得到了一个 O(n^2) 的动态规划解法。这个解法保证了平衡条件，同时通过替换操作最小化改动字符数。

线性动态规划：最少操作使字符串平衡（Minimum Operations to Balance a String） 题目描述 给定一个长度为 \( n \) 的只包含字符 '(' 和 ')' 的字符串 s 。定义一次操作：你可以将字符串中的 任意位置 的字符替换成另一个字符（即 '(' 变 ')' 或 ')' 变 '(' ）。你的目标是让字符串 平衡 。 平衡字符串的定义： 字符串中 '(' 和 ')' 的数量相等。 对于字符串的每一个前缀（从开头到任意位置的子串），其中 '(' 的数量必须 大于等于 ')' 的数量（即前缀中不会出现 ')' 比 '(' 多的情况，也就是经典的有效括号前缀条件）。 请你计算，最少需要多少次替换操作，才能将字符串 s 变成平衡字符串。 示例 1 ： 我们先明确：题目要求最终字符串满足两个条件：数量相等 + 前缀中左括号不少于右括号。 注意：操作是 替换 ，不是插入或删除。所以最终字符串长度不变，只是部分字符改变了。 我们从头思考。 逐步分析 第一步：理解平衡条件 对于一个最终平衡的字符串： 长度 n 必须是偶数 ，因为左右括号数量相等。 设最终字符串有 \( n/2 \) 个 '(' 和 \( n/2 \) 个 ')' 。 前缀条件：对于任何位置 \( i \)（1 ≤ i ≤ n），前缀中 '(' 的数量 ≥ ')' 的数量。 这其实就是经典的有效括号序列的 前缀条件 ，并且最终整个字符串的左右括号数相等。 第二步：问题转化 我们只能通过替换字符来改变字符串，不能改变长度。 设最终字符串中 '(' 的数量为 \( n/2 \)， ')' 的数量为 \( n/2 \)。 初始字符串中， '(' 的数量记为 leftCount ， ')' 的数量为 rightCount 。 如果我们直接强行让最终有 \( n/2 \) 个 '(' ，那么需要： 如果原串中 '(' 少于 \( n/2 \)，则少几个 '(' 就要把几个 ')' 改为 '(' 。 如果原串中 '(' 多于 \( n/2 \)，则多几个 '(' 就要把几个 '(' 改为 ')' 。 这样修改后，数量条件就满足了。但修改后的字符串不一定满足前缀条件。 所以，我们需要在满足前缀条件的前提下，尽量少替换。 第三步：动态规划状态设计 我们可以从左到右扫描字符串，记录当前前缀中 '(' 的数量与 ')' 的数量的差值（称为 平衡度 balance ），必须保持 balance ≥ 0。 同时，我们还要记录已经放置了多少个 '(' （因为最终必须有 \( n/2 \) 个 '(' ）。 定义状态： \( dp[ i][ j][ b] \) 表示考虑前 i 个字符，已经放置了 j 个 '(' （这 j 个 '(' 可能是原串的 '(' 没改，或者原串是 ')' 改成的 '('），并且当前平衡度 balance = b（即 '(' 比 ')' 多 b 个）的情况下，最少的替换操作次数。 但是这样状态维度高：i 最多 n，j 最多 n，b 最多 n。复杂度 O(n^3)，可能较大。我们需要优化。 第四步：优化状态设计 注意到最终必须有 \( n/2 \) 个 '(' ，所以 j 其实由最终目标固定了一半。但我们在扫描过程中可以决定每个位置是放 '(' 还是 ')' ，只要最终 j = n/2 且 balance 始终 ≥0，且 balance 最终为 0。 更常见的思路：贪心 + 动态规划。 有一个经典问题与此类似：给定初始括号串，可以翻转（即替换）括号，求最少的翻转次数使之成为有效括号序列。 解法：先确保最终左右括号数量均为 n/2，然后扫描决定哪些位置必须改为 '(' ，哪些必须改为 ')' 。 让我们直接推导递推关系。 设最终字符串为 t，满足： t 有 n/2 个 '('，n/2 个 ')'。 对于所有前缀，'(' 数量 ≥ ')' 数量。 定义 cost(i, ch) 为将 s[ i] 改为字符 ch 的代价：若 s[ i ] == ch 则代价 0，否则代价 1（因为一次替换）。 我们按顺序决定 t[ i ] 是 '(' 还是 ')'。 设 f(i, open, bal) 为考虑前 i 个字符，已经用了 open 个 '('，当前平衡度 bal = (open - close) = bal（即 '(' 比 ')' 多 bal 个）的最小代价。 其中 close = i - open 是已用的 ')' 数量，bal = open - close = 2* open - i。 限制： bal ≥ 0（前缀条件）。 open ≤ n/2（不能超过最终 '(' 数量）。 i - open ≤ n/2（不能超过最终 ')' 数量，即 close ≤ n/2）。 目标：f(n, n/2, 0)。 转移： 对于第 i 个位置（0-index），我们可以放 '(' 或 ')'。 如果放 '('： 前提是 open+1 ≤ n/2，且新的 bal' = bal+1 ≥ 0（自动满足，因为 bal≥0 时 bal+1>0）。 代价 = cost(i, '(')。 如果放 ')'： 前提是 i - (open+1) ≤ n/2？不对，放 ')' 时 open 不变，close+1，所以需要 close+1 ≤ n/2，即 i+1 - open ≤ n/2。 并且新的 bal' = bal-1 ≥ 0。 代价 = cost(i, ')')。 因此： 小心下标的处理。我们详细展开。 第五步：简化状态与迭代实现 我们可以减少一维，注意到 bal = 2* open - i，所以如果我们知道 i 和 open，bal 就确定了。 因此状态可以设为 f(i, open)，表示前 i 个字符中放了 open 个 '(' 的最小代价，并且中间过程 bal 始终 ≥0。 转移： 对于 i 从 1 到 n： 如果我们让 t[ i ] = '('，需要 open > 0（因为 open 是计数已放 '(' 数，但这里 open 表示前 i 个中 '(' 的总数，所以在放 '(' 时，新的 open' = open，对应上一步的 open-1 个 '('）。我们来精确推导： 设当前考虑完第 i 个字符，共有 open 个 '('。那么第 i 个字符有两种可能： 第 i 个字符是 '('：那么前 i-1 个字符中应有 open-1 个 '('，且那时平衡度 bal_ {i-1} = (open-1) - (i-1 - (open-1)) = 2* (open-1) - (i-1) = 2 open - i - 1。 这个值必须 ≥0（前缀条件在第 i-1 步时）。 转移到 f(i, open) = f(i-1, open-1) + cost(i, '(')，前提是 open≥1 且 2 open - i - 1 ≥ 0。 第 i 个字符是 ')'：那么前 i-1 个字符中应有 open 个 '('，且那时平衡度 bal_ {i-1} = 2 open - (i-1)。 现在在第 i 步放 ')'，新平衡度 bal_ i = 2 open - i，必须 ≥0。 所以需要 2 open - i ≥ 0。 转移到 f(i, open) = f(i-1, open) + cost(i, ')')，前提是 open ≤ i 且 2 open - i ≥ 0。 初始： f(0, 0) = 0，其余无穷大。 目标： f(n, n/2)，前提是 n 为偶数（否则不可能平衡）。 第六步：边界与答案 最终答案就是 f(n, n/2)，其中 n 必须是偶数，否则返回 -1 或不可能。 复杂度 O(n^2)，但 n 可以较大，不过这个状态数 1000* 1000 可能较大。我们可以优化，注意到 open 的取值范围受前缀条件限制，所以很多状态不可达。但作为通用解法，我们实现时可以只计算可达状态。 第七步：示例推演 例：s = "())("，n=4 偶数。 目标 open=2。 i=1（字符 s[ 0 ]='('）： 放 '('：open=1，需要 2* 1 - 1 - 1 = 0 ≥ 0，代价 0，f(1,1)=0。 放 ')'：open=0，需要 2* 0 - 1 = -1 <0，不允许。 其余 open 值无穷。 i=2（字符 s[ 1 ]=')'）： open 从 0..2。 open=1：可以从 f(1,1) 放 ')' 得到：需要 2 1 - 2 = 0 ≥ 0，代价 1，f(2,1)=1。 或者从 f(1,0) 放 '('，但 f(1,0) 不存在。 open=2：可以从 f(1,1) 放 '('：需要 2 2 - 2 - 1 = 1 ≥ 0，代价 0，f(2,2)=0。 i=3（字符 s[ 2 ]=')'）： open=1：从 f(2,1) 放 ')'：2 1 - 3 = -1 <0 不允许。从 f(2,0) 放 '(' 不存在。 open=2：从 f(2,2) 放 ')'：2 2 - 3 = 1 ≥0，代价 1，f(3,2)=1。 从 f(2,1) 放 '('：需要 open≥1 且 2 2 - 3 -1 = 0≥0，代价 1，得 f(3,2)=min(1, 1+1)=1。 open=3：从 f(2,2) 放 '('：需要 2 3 - 3 -1 = 2≥0，代价 0，f(3,3)=0。 i=4（字符 s[ 3 ]='('）： 目标 open=2。 open=2：从 f(3,2) 放 ')'：需要 2 2 - 4 = 0≥0，代价 0（因为 s[ 3]='(' 要变成 ')' 代价 1？不对，这里 cost(4, ')') 是 s[ 3] 改为 ')' 的代价，原 s[ 3 ]='('，所以代价 1），所以 f(4,2)=1+1=2。 从 f(3,1) 放 '('：f(3,1) 不存在。 open=3：从 f(3,3) 放 ')'：需要 2 3 - 4 = 2≥0，代价 1，f(4,3)=0+1=1。 从 f(3,2) 放 '('：需要 2 3 - 4 -1 = 1≥0，代价 0，f(4,3)=min(1, 1+0)=1。 open=4：从 f(3,3) 放 '('：需要 2 4 - 4 -1 = 3≥0，代价 0，f(4,4)=0。 最终 f(4,2)=2？但前面我们手工算似乎 1 次操作就行？检查：s="())(" 一种改法：s[ 2]=')' 改为 '('，得到 "(()("，现在：'(' 数量 3，')' 数量 1，不符合数量相等（需要 2 和 2）。还要再改一个 '(' 为 ')'，比如 s[ 3 ]='(' 改为 ')'，得到 "(())"，这个串平衡吗？前缀：'(' 数量始终 ≥')' 数量，且最终各 2 个，平衡。操作次数 2。 另一种：s[ 0 ]='(' 改为 ')'，得到 ")))("，不行。 似乎最少就是 2 次。但我之前以为 1 次可能，验证不行。所以我们的 dp 结果 f(4,2)=2 是对的。 因此示例答案应该是 2，不是之前示例给的 1（原题示例可能给错，或者是不同变种）。 最终算法步骤 如果 n 是奇数，返回 -1（不可能平衡）。 初始化 dp 数组，dp[ 0][ 0 ] = 0，其他为无穷大。 遍历 i = 1 到 n： 遍历可能的 open 数（从 0 到 i）： a. 如果 open ≥ 1 且 2 open - i - 1 ≥ 0，则 dp[ i][ open] = min(dp[ i][ open], dp[ i-1][ open-1] + (s[ i-1] != '('))。 b. 如果 2 open - i ≥ 0，则 dp[ i][ open] = min(dp[ i][ open], dp[ i-1][ open] + (s[ i-1] != ')')). 答案为 dp[ n][ n/2 ]。 这样我们就得到了一个 O(n^2) 的动态规划解法。这个解法保证了平衡条件，同时通过替换操作最小化改动字符数。