题解 | 括号区间匹配

#include <bits/stdc++.h>
#include <climits>
using namespace std;

const int N = 101;
string str;
int dp[N][N];

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

int main(){
    cin>>str;
    int n = str.size();
    str = ' ' + str;

    for(int i  = 1;i<=n;i++) dp[i][i] = 1;

    for(int i = 1;i<n;i++){
        for(int j = 1;j+i<=n;j++){
            int k = j + i;
            dp[j][k] = INT_MAX;
            if(check(str[j],str[k])) {
                dp[j][k] = min(dp[j][k],dp[j+1][k-1]);
            }
            for(int k2 = j;k2<k;k2++){
                dp[j][k] = min(dp[j][k],dp[j][k2]+dp[k2+1][k]);
            }
        }
    }    
    cout<<dp[1][n];

    return 0;
}

只有一个的时候需要多加一个才能匹配，如果str[j]==str[k]，那么dp[j][k] = min(dp[j][k],dp[j+1][k-1])，否则 dp[j][k] = min(dp[j][k],dp[j][k2]+dp[k2+1][k]);

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344