题目拿到手看了一下，是要括号配对（有两种情况），确实和 1222.密码脱落 很相似，因为都是 配对问题，状态转移都是和区间的边界值有关，这题很容易想到$区间dp$ 。

$先附上其他大佬的yan氏dp的分析图：$传送门

$老样子按照dp步骤来：$

$1.状态定义:dp(i,j)表示区间[i,j]中添加字符使其成为GBE的集合，属性为min$

$2.状态转移（这一步比较难）：$
$这个集合由哪些组成呢？按照最后不同的一步来，假如i与j匹配，只需要从dp(i+1,j-1)那个集合转移过来$

假如不匹配，那似乎应该从$dp(i+1,j)或者dp(i,j-1)$来,这里是最大的坑。

因为题目中有个条件是$AB$都是$GBE$,那么$AB$也是。
那如果字符串是()[]，需要匹配是0个，但是第一个和最后一个是不匹配的，就会转移错误。

$所以，我们需要枚举区间[i,j]里的每个分隔点，看是否会出现题目出现的第三种AB都是GBE$（第二种已经被包含），使得需要添加的更少。

$dp(i,j)=dp(i+1,j-1)(s[i]==s[j])$
$dp(i,j)=min(dp(i,j),dp(i,k)+dp(k+1,j))(i<=k<=j)$

3.初始化：

$全部是INF，因为要取最小值，不合法的状态可以在递推的时候变成0，或者改变k的范围。但是在这道题$里，不影响。

$或者：一开始全部为0，然后每次在到一个新的[i,j]区间时全部设成INF，这样不合法区间就为0，就不用特$判。

4.递推顺序：

$因为要用到后面的状态，所以i要逆序枚举。$

5.注意点：

1.当枚举分割点的时候，已经不需要在看小区间内是否端点匹配了，因为更小的区间的最小值已经在之前更新过了。
$2.当i=j-1时，s[i]和s[j]match的时候，dp(i,j)应该为0，但是dp(i+1,j-1)为不合法状态为INF，$如果转移过来需要特判。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<climits>
#define x first
#define y second
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 100 + 5;
int dp[N][N];
char s[N];

bool match(int i, int j){
    if (s[i] == '[' && s[j] == ']') return true;
    if (s[i] == '(' && s[j] == ')') return true;
    return false;
}

int main(void){
    scanf("%s", s);
    int n = strlen(s);

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            dp[i][j] = 1e9;

    for (int i = n - 1; i > -1; --i){
        for (int j = i; j < n; ++j){
            if (i == j){
                dp[i][j] = 1; continue;
            }
            if (match(i, j)) dp[i][j] = min(dp[i][j], (i == j - 1 ? 0 : dp[i + 1][j - 1]) );
            for (int k = i; k <= j; ++k){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
            // printf("(%d, %d)%d ", i, j, dp[i][j]);
        }
        // cout << endl;
    }

    cout << dp[0][n - 1];
    return 0;
}