C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 492K, 提交时间: 2019-08-21 16:43:28

#include "bits/stdc++.h"
#define rep(i,s,e) for(int i = s;i<=e;i++)
using namespace std;
const int maxn = 110;
int n;
char s[maxn];
int dp[maxn][maxn];
int main()
{
    scanf("%s",s+1);
    n = (int)strlen(s+1);
    rep(delta, 1, n-1)
    rep(i, 1, n-delta)
    {
        int j = i+delta;
        if(s[i] == '(' && s[j] == ')' ||
           s[i] == '[' && s[j] == ']')
            dp[i][j] = dp[i+1][j-1]+2;
        for(int k = i;k<j;k++)
            dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
    }
    cout << n-dp[1][n] << endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 412K, 提交时间: 2023-03-06 15:22:03

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

C++ 解法, 执行用时: 4ms, 内存消耗: 436K, 提交时间: 2022-06-07 14:08:31

#include<bits/stdc++.h>
using namespace std;
int n,f[111][111];
char S[11111];
int main()
{
	scanf("%s",S+1);
	n=strlen(S+1);
	for(int i=1; i<=n; i++)
	for(int j=1; j+i-1<=n; j++)
	{
		int l=j,r=j+i-1;
		if(S[l]=='('&&S[r]==')'||S[l]=='['&&S[r]==']')
		f[l][r]=max(f[l][r],f[l+1][r-1]+2);
		for(int k=l; k<r; k++)
		f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
	}
	cout<<n-f[1][n]<<endl;
	return 0;
}