需要多少次翻转括号串的子字符串上的所有括号的操作才能使字符串“正确”？

Question

如果每个左括号后面都有一个相应的右括号，并且每个右括号前面都有一个相应的左括号，我称一串括号为“正确”。例如

(())()((()()))

是一个正确的字符串并且

)()()(

是一个不正确的字符串。

操作包括获取输入字符串的连续子序列并“翻转”该子序列中的每个括号。

给定任意括号串（偶数长度），任务是找到将其更改为“正确”括号串所需的最少数量的此类操作。

看待这个问题的另一种方法是拥有一个由 +1 和 -1 组成的字符串，并尝试找到使该字符串的每个前缀非负所需的最少操作数（将区间上的每个数字乘以 -1）并且每个后缀都是非正的。

Answer 1

DP在Yuval Filmus的评论中建议实际上：我们可以解决 $ \ mathcal {o}（n ^ {2}）$ 的问题DP。

首先注意，我们可能假设不允许间隔重叠。采用任何两种重叠间隔 $ [a，b）$ 和 $ [c，d）$ 。 wlog $ a \ leq c $ 。然后我们可以用间隔 $ [a，c）$ 和 $ [\ min（b，d ），\ max（b，d））$ 不重叠，总长度较短，覆盖完全相同的元素。

用 $ 1 $ ，带有 $ - 1 $ 的关闭括号。现在问题对应于应用最小操作数“乘以<跨度class=”math-container“> $ - 1 $ ”，使得每个前缀具有非负和，并且整个数组上的总和是零。

我们将左右构建解决方案。在每个位置，我们可以开始间隔，或结束活动间隔。

let $ dp [m] [s] [0] $ 表示我们需要使用的最小间隔数，使得第一个 $ m $ 元素是非负面的，第一个 $ m $ 元素是 $ s $ ，我们没有活动间隔。同样<跨越类=“math-container”> $ dp [m] [s] [1] $ 是与我们确实有活动间隔的相同的值。

如果 $ m $ th值是 $ 1 $ ，对于 $ 0 \ leq s \ leq m $ 我们设置

• $ dp [m] [s] [0]= dp [m-1] [s-1] [0] $
• $ dp [m] [s] [1]= dp [m-1] [s + 1] [1] $

否则我们设置

• $ dp [m] [s] [0]= dp [m-1] [s + 1] [0] $
• $ dp [m] [s] [1]= dp [m-1] [s-1] [1] $ 。

然后我们结束并开始间隔，设置

• $ dp [m] [s] [0]=min（dp [m] [s] [0]，dp [m] [1]） $
• $ dp [m] [s] [1]=min（dp [m] [s] [1]，dp [m] [s] [0] + 1）$

基本情况是 $ dp [0] [0] [0]= 0 $ ， $ dp [0 ] [0] [1]= 1 $ 。

有 $ \ mathcal {o}（n ^ {2}）$ 状态，我们做 $ \ mathcal {o}（1）$ 工作要计算它们中的每一个，因此算法在 $ \ mathcal {o}中运行（n ^ {2}）$ 。 DP可以通过仅存储 $ dp的值，使用 $ \ mathcal {o}（n）$ \ mathcal {o}（n）$ \ mathcal {o} $ 当前 $ m $ 。

以下是算法的C ++实现。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}

.

Answer 2

好问题！

这是用更通俗的术语来说的问题。

平衡括号

如果我们可以通过重复删除子字符串“()”将其变为空字符串，则一串括号是平衡的。例如，空字符串“()”和“(())()((()()))”是平衡的，但“())”和“)()()(”都不平衡。

显然，平衡字符串必须以“(”开头，以“)”结尾。它的长度也必须均匀。

平衡弦的最少运算问题

让 s 是长度为括号的非空字符串 n. 。我们唯一可以执行的操作是翻转子字符串中的每个括号，即将字符串中的某些连续字符将每个“(”更改为“)”，将每个“)”更改为“(”。问题是如何找到最少的操作数 s 均衡。

动态规划方法

适当的子问题是什么？他们是 dp[i][j] 为了 0 <= i < j < n, ， 在哪里 dp[i][j] 是平衡索引之间子串的最少操作数 i 和索引 j 包括的。所需的最小平衡操作数 s 是 dp[0][n-1].

由于任何奇数长度的字符串都无法平衡，因此从现在开始我们将把注意力限制在偶数长度的字符串上。

基本情况 dp[i][i+1] 如果之间的子串为 0 i 和 i+1 是平衡的，即“()”。否则为 1。

递推关系我将使用Java来定义递归关系。

void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

递归关系来自平衡串的以下众所周知的性质。非空字符串是平衡的当且仅当它是两个平衡字符串或“(”后跟平衡字符串后跟“)”的串联。

之前的处理 for 循环，设置 min 成为 dp[i + 1][j - 1] 加 0、1 或 2，来自这样的事实：“(”后面跟着一个平衡字符串，后面跟着“)”一定是一个平衡字符串。

处理过程在 for 循环，它试图缩小 min 到 dp[i][k] + dp[k + 1][j] 某些负 0 或 1 k 那是之间 i 和 j, ，来自两个平衡字符串的串联必须是平衡字符串这一事实。

该方法的时间复杂度为 $O(n^3)$. 。空间复杂度为 $O(n^2)$.

“最不平衡”弦的长度

不能通过少于 2 次操作平衡的字符串的最小长度是 4。例如， ”）（（（”

不能通过少于 3 次操作平衡的字符串的最小长度是 10。例如， ”）（（（（（（））（”

不能通过少于 4 次操作平衡的字符串的最小长度是 22。例如， ”）（（））））（（（（（（（（（（（（））（”。

问题：至少需要 5 次操作的字符串的最小长度是多少？据我计算，它必须大于28。然而，我的计算不足以确定实际值。我们计算这些最小长度的速度有多快？