给定一个长度为 n
的字符串 s
，字符串由 (, ), [, ] 组成，问其中最长的合法子序列有多长？也就是说，我们要找到最大的 m
，使得存在 i1,i2,…,im
满足 1≤i1<i2<⋯<im≤n
并且 si1si2…sim
是一个合法的括号序列。
合法的括号序列的定义是：
空串是一个合法的括号序列。
若 A 是一个合法的括号序列，则 (A), [A] 也是合法的括号序列。
若 A, B 都是合法的括号序列，则 AB 也是合法的括号序列。
输入格式
第一行一个整数 n
。
接下来一行，一个长度为 n
的字符串 s
。
输出格式
一个数，表示答案。
样例输入
10
]]][()]])[
样例输出
4
数据规模
对于所有数据，保证 1≤n≤500
。
区间DP
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=510;
char ch[N];
int f[N][N];
int main()
{
int n;
cin>>n;
//对于f[i][j]可能为[A],(A)或者AB
for(int i=1;i<=n;++i)
{
cin>>ch[i];
f[i][i]=0;
}
for(int l=2;l<=n;++l)
for(int i=1;i<=n;++i)
{
int j=i+l-1;
if(j>n) break;
if((ch[i]=='('&&ch[j]==')')||(ch[i]=='['&&ch[j]==']'))
f[i][j]=f[i+1][j-1]+2;
for(int k=i;k<j;++k)
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
}
cout<<f[1][n]<<'\n';
}