题解 | 括号区间匹配

水题，区间dp即可，转移是显然（？）的。

#include<bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::string s;
    std::cin >> s;
    int n = s.size();

    std::vector dp(n, std::vector<int>(n, n));
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    std::map<char, int> mp;
    mp['('] = -1;
    mp[')'] = 1;
    mp['['] = -2;
    mp[']'] = 2;

    for (int i = 1; i < n; i++) {
        dp[i][i - 1] = 0;
    }

    for (int l = 2; l <= n; l++) {
        for (int i = 0; i + l - 1 < n; i++) {
            dp[i][i + l - 1] = std::min(dp[i][i + l - 1], dp[i + 1][i + l - 2] + (mp[s[i]] < 0 && mp[s[i]] + mp[s[i + l - 1]] == 0 ? 0 : 2));
            for (int j = i; j < i + l - 1; j++) {
                dp[i][i + l - 1] = std::min(dp[i][i + l - 1], dp[i][j] + dp[j + 1][i + l - 1]);
            }
        }
    }

    std::cout << dp[0][n - 1];

    return 0;
}

https://www.nowcoder.com/discuss/727521113110073344