5

与えられた質問：

文字列の左括弧と右括弧を適切にペアリングできる場合、括弧の文字列はバランスが取れていると言われます。たとえば、文字列 "（（））"と "（）（）"は両方ともバランスが取れていますが、文字列 "（（）（"はバランスが取れていません。括弧で構成される長さn
の文字列Sが与えられた場合、次のようになります。バランスの取れたSの最長のサブシーケンスを見つける動的計画法を使用して、O（n ^ 3）時間でSの最長のバランスの取れたサブシーケンスを見つけるアルゴリズムを設計します。

私のアプローチ：
与えられた文字列を仮定します：S [1 2 ... n]
S [i] =='）'の場合、有効なサブシーケンスはS[i]で終了できます。 S[i]の前に少なくとも1つの未使用のオープニングブレース。これはO（N）で実装できます。

#include<iostream>
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.length(), o_count = 0, len = 0;
    for(int i=0; i<n; ++i){
        if(s[i] == '('){
            ++o_count;
            continue;
        }
        else if(s[i] == ')' && o_count > 0){
            ++len;
            --o_count;
        }
    }
    cout << len << endl;
    return 0;
}

いくつかのテストケースを試しましたが、正常に機能しているようです。ここで何かが足りませんか？そうでない場合、この問題のO（n ^ 3）動的計画法ソリューションを設計するにはどうすればよいですか？これは私が使用しているサブシーケンス

の定義です。

ありがとう！

4

2 に答える 2

2

DPの場合O(n^3)、これは機能するはずです。

dp[i, j] = longest balanced subsequence in [i .. j]
dp[i, i] = 0
dp[i, i + 1] = 2 if [i, i + 1] == "()", 0 otherwise

dp[i, j] = max{dp[i, k] + dp[k + 1, j] : j > i + 1} in general

これは、最適な行列の連鎖乗積と同様に実装できます。

あなたのアルゴリズムも私には正しいようです。たとえば、この問題を参照してください。

http://xorswap.com/questions/107-implement-a-function-to-balance-parentheses-in-a-string-using-the-minimum-nu

ソリューションが基本的にあなたのものと同じであるところ。

あなたは余分な括弧を無視しているだけなので、なぜそれが機能しないのかわかりません。

于 2012-10-25T18:00:42.163 に答える
1

O(n^2)Java での時空間 DP ソリューションを次に示します。

public int findLongestBalancedSubsequence(String seq, int n) {
    int[][] lengths = new int[n][n];

    for (int l = 1; l < n; l++) {
        for (int i = 0; i < n - l; i++) {
            int j = i + l;
            // Ends are balanced.
            if (seq.charAt(i) == '(' && seq.charAt(j) == ')') {
                // lengths[i, j] = max(lengths[i + 1, j - 1] + 2, lengths[i + 1, j] + 
                // lengths[i, j - 1] - lengths[i + 1, j - 1])
                if (lengths[i + 1][j - 1] + 2 > lengths[i + 1][j] +
                    lengths[i][j - 1] - lengths[i + 1][j - 1])
                    lengths[i][j] = lengths[i + 1][j - 1] + 2;
                else
                    lengths[i][j] = lengths[i + 1][j] +
                        lengths[i][j - 1] - lengths[i + 1][j - 1];
            // Ends are not balanced.
            } else {
                // lengths[i, j] = max(lengths[i + 1, j], lengths[i, j - 1])
                if (lengths[i + 1][j] > lengths[i][j - 1])
                    lengths[i][j] = lengths[i + 1][j];
                else
                    lengths[i][j] = lengths[i][j - 1];
            }
        }
    }

    return lengths[0][n - 1];
}
于 2016-07-18T15:26:09.300 に答える