题解 | 括号区间匹配

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

string s;
int dp[105][105];

// 判断两个括号能否匹配
bool match(char a, char b) {
    return (a == '(' && b == ')') || (a == '[' && b == ']');
}

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

    memset(dp, 0, sizeof(dp));

    // 长度为1的子串需要插入1个括号
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;

    // 枚举区间长度len，从2开始逐渐增加
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = 1e9;

            // 如果两端配对
            if (match(s[i], s[j])) {
                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;
}