5

给定问题：

如果字符串中的左括号和右括号可以正确配对，则称该字符串是平衡的。例如，字符串 "(())" 和 "()()" 都是平衡的，而字符串 "(()(" 是不平衡的。给定一个由括号组成的长度为n
的字符串S，假设你想找到S的最长平衡子序列。使用动态规划，设计一种算法，在O(n^3)时间内找到S的最长平衡子序列。

我的方法：
假设给定字符串： S[1 2 ... n]
如果 S[i] == ')' 即 S[i] 是右大括号并且存在，则有效的子序列可以在 S[i] 处结束在 S[i] 之前至少有一个未使用的左大括号。这可以在 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

对于O(n^3)DP，我认为这应该可行：

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 回答