括号配对

解法:回文子序列的扩展 + DP

参考大佬题解:
https://www.acwing.com/solution/content/17886/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110
#define INF 100000000
using namespace std;

int n;
int f[N][N];

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 ++)
        {
            int j = i + len - 1;
            f[i][j] = INF;
            if(is_match(s[i],s[j]))  f[i][j] = f[i+1][j-1];
            f[i][j] = min(f[i][j], min(f[i][j-1],f[i+1][j])+1);

            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;
}