区间DP

该题类似于密码脱落和石子合并两题的结合，因为若括号序列是回文串，那么一定是合法的。但是该题新加了一个条件即()[]这样并列的括号也是合法的。

$ 时间复杂度O(N^3)，空间复杂度O(N^2) $

参考文献

蓝桥杯辅导课

AC代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e3 + 10;

string s;
int n;
int f[N][N];

bool check(char a ,char b){
    if (a == '(' && b == ')') return true;
    if (a == '[' && b == ']') return true;
    return false;
}

int main(){
    //读入
    cin >> s;
    n = s.size();

    //区间DP
    for (int len = 1 ; len <= n ; len ++){
        for (int i = 0 ; i + len - 1 < n ; i ++){
            int j = i + len - 1;
            if (len == 1) f[i][j] = 1;//初始化
            else {
                f[i][j] = 1e9;
                if (check(s[i], s[j])) f[i][j] = f[i + 1][j - 1];
                else f[i][j] = f[i + 1][j - 1] + 2;
                f[i][j] = min(f[i][j], min(f[i + 1][j], f[i][j - 1]) + 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];
    return 0;
}