算法1

思路：动态规划，集合为f[l][j]表示向字符串中l~r添加字符使其变成GBE的所有所有方案的集合，属性：求最小值

定义：i从左走，j从右走，因为i从0开始，所以j从i+len-1开始

我们可以讲问题处理成两部分：第一部分是处理括号，包含(i,j),(i,)(,j)()四种情况，分别为左右括号都存在都存在，只有左括号,或者只有右括号，或者左右括号都没有，第二部分是字母A,B

对于左右括号都存在，他的区间范围是f[i+1,j-1]里面都包含，如果只有左括号，说明区间范围是f[i,j-1],同理如果只有右括号，区间范围是f[i+1,j],如果是都不存在，区间范围是f[i+1,j-1]去寻找下一对，这里注意要+2，

最后统计所有情况，求f[i,j]=f[i-1,j] | f[i,j-A]

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=110,INF=100000000;

int n;
int f[N][N];//集合f[l][j]表示向字符串中l~r添加字符使其变成GBE的所有所有方案的集合

bool is_match(char l,char r)//判断符号匹配
{
    if(l=='(' &&r==')') return true;
    if(l=='[' && r==']') return true;
    return false;
}


int main()
{
    string s;
    cin>>s;
    n=s.size();


    for (int len = 1; len <= n; len ++ )
        for (int i = 0; i + len - 1 < n; i ++ )//i从0开始
        {
            int j = i + len - 1;//让j从最右边开始往回走
            f[i][j] = INF;//初始值定义为最大
            if (is_match(s[i], s[j])) f[i][j] = f[i + 1][j - 1];//如果两个匹配，说明包含的区间范围是f[i+1,j-1]
            if (j >= 1) f[i][j] = min(f[i][j], min(f[i][j - 1], f[i + 1][j]) + 1);//在j没有到达最左边之前，我们的题意是求最小值

            for (int k = i; k < j; k ++ )
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
        }


    cout<<f[0][n-1]<<endl;
    return 0;
}