翻转算法

Question

我有一个包含不同类型括号的字符串 s：() 和 []。我怎样才能平衡这种类型的字符串与尽可能少的反转次数？我可以用任何其他支架替换任何支架。

例如：[)(] 的成本为 2，它变为 [()]。 [](( 的成本是 1，它变成 []() 。 [(]) 不平衡。

更复杂的例子：)[)([)())]可以4次变([])[(())]，也可以3步变[()(()())]，这是最少的变数使其平衡。

我该如何解决这个问题？

Answer 1

我想到的第一个方法是 O(n^3) 动态规划。

设 match(i, j) 为使 s[i] 和 s[j] 为 () 或 [] 必须进行的替换次数。所以 match(i, j) 可以是 0、1 或 2.

考虑 dp[i][j] = the minimum cost to balance the subsequence from i to j in your brackets array。现在您将 dp[i][i + 1] 定义为：

dp[i][i + 1] = match(i, i + 1)

现在的一般规则是，我们对任何 i < p < j 取 dp[i + 1][j - 1] + match(i, j) 和 min(dp[i][j], dp[i][p] + dp[p + 1][j]) 之间的总体最小值。显然，结果将保存在dp[1][n]中。有一个 C++ 解决方案（我还会在大约 15 分钟内上传一个 python 程序，当我完成它时 - python 不太强大：P）。

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

int dp[100][100];
string s;
int n;

int match(char a, char b) {
    if (a == '(' && b == ')') {
        return 0;
    }
    if (a == '[' && b == ']') {
        return 0;
    }
    if ((a == ')' || a == ']') && (b == '(' || b == '[')) {
        return 2;
    }
    return 1;
}

int main() {
    cin >> s;
    n = s.length();
    s = " " + s;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = 0x3f3f3f3f;
        }
    }    

    for (int i = 1; i < n; ++i) {
        dp[i][i + 1] = match(s[i], s[i + 1]);
    }

    for (int k = 3; k <= n; k += 2) {
        for (int i = 1; i + k <= n; ++i) {
            int j = i + k;
            dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + match(s[i], s[j]));
            for (int p = i + 1; p <= j; p += 2) {
                dp[i][j] = min(dp[i][j], dp[i][p] + dp[p + 1][j]);
            }
        }
    }
    cout << dp[1][n] << '\n';
    /*for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }*/
    return 0;
}

编辑：

给你Python :)

s = input()
n = len(s)
inf = 0x3f3f3f3f

def match(x, y):
    if x == '(' and y == ')':
        return 0
    if x == '[' and y == ']':
        return 0
    if (x == ')' or x == ']') and (y == '(' or y == '['):
        return 2
    return 1

# dp[i][j] = min. cost for balancing a[i], a[i + 1], ..., a[j]
dp = [[inf for j in range(n)] for i in range(n)]

for i in range(n - 1):
    dp[i][i + 1] = match(s[i], s[i + 1])

for k in range(3, n, 2):
    i = 0
    while i + k < n:
        j = i + k
        dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + match(s[i], s[j]))
        for p in range(i + 1, j, 2):
            dp[i][j] = min(dp[i][j], dp[i][p] + dp[p + 1][j])
        i += 1

print(dp[0][n - 1])
#for i in range(n):
#    for j in range(n):
#        print(dp[i][j], end = ' ')
#    print()

翻转算法

Flipping algorithm

string

algorithm

brackets

balance