的S最长子是平衡 [英] Longest subsequence of S that is balanced
问题描述
考虑的问题:
一个字符串,括号被认为是
平衡,如果字符串中的左,右括号可以适当地配对了。例如,字符串(())和()()都是平衡的,而字符串(()(是不
均衡。
给定一个字符串的取值长度 N 括号组成的,假设你想找到的最长的子序列的取值这是平衡的。使用动态规划,设计一个算法,发现的最长的平衡子的取值在为O(n ^ 3)的时间。
Given question:
A string of parentheses is said to be
balanced if the left- and right-parentheses in the string can be paired off properly. For example, the strings "(())" and "()()" are both balanced, while the string "(()(" is not
balanced.
Given a string S of length n consisting of parentheses, suppose you want to find the longest subsequence of S that is balanced. Using dynamic programming, design an algorithm that finds the longest balanced subsequence of S in O(n^3) time.
我的做法:
假设给定的字符串:S [1 2 ... N]
有效的子序列可以在S [I]当且仅当S [I] ==')'结尾,即S [i]为一个右括号,并至少存在一个未使用的开括号previous到S [1]。它可以在O(N)来实现。
My approach:
Suppose given string: S[1 2 ... n]
A valid sub-sequence can end at S[i] iff S[i] == ')' i.e. S[i] is a closing brace and there exists at least one unused opening brace previous to S[i]. which could be implemented in 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)动态规划为这个问题的解决?_爱 这是子我使用的定义。
I tried a couple of test cases and they seem to be working fine. Am I missing something here? If not, then how can I also design an O(n^3) Dynamic Programming solution for this problem?
This is the definition of subsequence that I'm using.
谢谢!
推荐答案
有关为O(n ^ 3)
DP这应该工作,我认为:
For O(n^3)
DP this should work I think:
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
这可以实现类似于如何最优的矩阵链乘法是。
This can be implemented similar to how optimal matrix chain multiplication is.
您算法还似乎是正确的我,看到例如这个问题:
Your algorithm also seems correct to me, see for example this problem:
<一个href="http://xorswap.com/questions/107-implement-a-function-to-balance-parentheses-in-a-string-using-the-minimum-nu" rel="nofollow">http://xorswap.com/questions/107-implement-a-function-to-balance-parentheses-in-a-string-using-the-minimum-nu
当解决方案基本都是一样的你。
Where the solutions are basically the same as yours.
您只忽略了额外的支架,所以我不明白为什么它是行不通的。
You are only ignoring the extra brackets, so I don't see why it wouldn't work.
这篇关于的S最长子是平衡的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!