题解 | 括号区间匹配

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
int dp[MAXN][MAXN];

int main()
{
    string s; cin >> s;
    int n = s.size();
    
    //对不括号不匹配的区间就标记为1操作
    for (int i = 0; i < n-1; i++) {
        if ((s[i] == '(' && s[i+1] == ')') || (s[i] == '[' && s[i+1] == ']')) {
            dp[i][i+1] = 0;
        } else {
            dp[i][i+1] = 1;
        }
    }

    //记得要从单个长度查起，因为后面的状态会依赖前面的状态
    for (int len = 0; len < n; len++) {
        for (int i = 0; i < n - len; i++) {
            int j = i + len;
            //先枚举分割点，然后枚举左右括号的匹配情况
            dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1);
            
            //特判相同情况
            if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']')) {
                dp[i][j] = min(dp[i][j], 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]);
            }
        }
    }
    cout << dp[0][n-1] << endl;
    return 0;
}