6669: 括号配对 区间dp

描述

Hecy 又接了个新任务：BE 处理。BE 中有一类被称为 GBE。

以下是 GBE 的定义：

空表达式是 GBE

如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE

如果 A 与 B 都是 GBE，那么 AB 是 GBE。

输入

输入仅一行，为字符串 BE。

对于 100% 的数据，输入的字符串长度小于 100。

输出

输出仅一个整数，表示增加的最少字符数

样例输入

 [])

样例输出

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10,inf = 0x3f3f3f3f;
int n,f[N][N];
string s;
int check(char a,char b)
{
    return (a=='['&&b==']' || a=='('&&b==')');
}
void dp()
{
    for(int i=0;i<n;i++)
        f[i+1][i] = 0,f[i][i] = 1;
    for(int i=n-2;i>=0;i--) //左端点 
        for(int j=i+1;j<n;j++) //右端点 
        {
            f[i][j] = n;
            if(check(s[i],s[j]))f[i][j] = min(f[i][j],f[i+1][j-1]); //比较当前区间ij和更小的区间i+1 j-1的大小 
            for(int k=i;k<j;k++) //遍历左右区间以k为中间点寻找最优解 
                f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]);
        }
}
int main()
{
    cin>>s;
    n = s.length();
    dp();
    printf("%d",f[0][n-1]);
     return 0;
}