翻轉算法

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 < jdp[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()