1572 括号配对 一本通

dp[i][j]表示从i到j有几个完成配对

状态转移分两部

• dp[l][r]=max(dp[l+1][r-1]+2,dp[l][r]);

//+2是完成一对括号的匹配，共两个字符

• dp[l][r]=max(dp[l][k]+dp[k+1][r],dp[l][r]);

//类似floyd

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
#define N 105
char s[N];
int dp[N][N],n;
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    rep(i,1,n)
        for(int j=1;j+i-1<=n;j++)
        {
            int l=j,r=i+j-1;
            if((s[l]=='(' && s[r]==')' )|| (s[l]=='[' && s[r]==']'))
                dp[l][r]=max(dp[l+1][r-1]+2,dp[l][r]);
            rep(k,l,r-1)
                dp[l][r]=max(dp[l][k]+dp[k+1][r],dp[l][r]);
        }
    printf("%d\n",n-dp[1][n]);
    return 0;
}

1572 括号配对 一本通

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11635599.html