平衡的S的最长子序列

Question

给出的问题:

如果字符串中的左括号和右括号可以正确配对,则称一串括号被平衡.例如,字符串"(())"和"()()"都是平衡的,而字符串"(()("不平衡.
给定长度为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)动态规划解决方案呢？

这是我正在使用的子序列的定义.

谢谢!

Answer 1

对于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

其中解决方案与您的基本相同。

您只是忽略了额外的括号，所以我不明白为什么它不起作用。