题解 | 括号区间匹配

// 并列，嵌套两种方法
// 思路s[l...r]范围内至少插入多少字符能让它变正确
// 两头端点的讨论和划分点的讨论揉在一起的题
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int f2(string& s,int l,int r,vector<vector<int>>& f){
    // base case:
    // l==r,不管剩哪一个字符都缺一个
    if(l==r){
        return 1;
    }
    // +这个base case 之后下面的边界就会少扣一些
    if(l+1==r){
        if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']')){
            return 0;
        }
        return 2;
    }
    // 正常情况：
    // [l...r]范围字符数量大于等于3
    if(f[l][r]!=-1){
        return f[l][r];
    }
    // 两种可能性展开
    int p1=INT_MAX;
    // l位置和r位置可以自我消化(本来就是配对的)
    if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']')){
        p1=f2(s,l+1,r-1,f);//那就看看中间范围上要插入几个
    }
    int p2=INT_MAX;
    // 基于每个划分点做可能性划分
    for(int k=l;k<r;k++){
        // l...k k+1...r
        // 来一个k就计算左侧需要几个，右侧需要几个加起来
        // 枚举所有可能的k,那其中划分这种可能的最小值抓出来
        p2=min(p2,f2(s,l,k,f)+f2(s,k+1,r,f));
    }
    int ans=min(p1,p2);
    f[l][r]=ans;
    return ans;
}
void sol(){
    string s;cin>>s;
    int n=s.size();
    vector<vector<int>> f(n,vector<int>(n,-1));
    cout<<f2(s,0,s.size()-1,f);
}
signed main(){
    int T;T=1;
    // cin>>T;
    while(T--){
        sol();
    }
    return 0;
}