括号序列

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
char que[101];
bool cal[101][101];
int len,dps[101][101];
void dfs(int i,int j)
{
	if(cal[i][j])return;
	if(i>j)return;
	if(i==j){
		dps[i][j]=1;
		return;
	}
	if((que[i]=='('&&que[j]==')')||(que[i]=='['&&que[j]==']')){
		dfs(i+1,j-1);
		dps[i][j]=dps[i+1][j-1];
	}
	if((que[i]=='('&&que[j]!=')')||(que[i]=='['&&que[j]!=']')){
		dfs(i+1,j);
		dps[i][j]=min(dps[i][j],dps[i+1][j]+1);
	}
	if((que[i]!='('&&que[j]==')')||(que[i]!='['&&que[j]==']')){
		dfs(i,j-1);
		dps[i][j]=min(dps[i][j],dps[i][j-1]+1);
	}
	for(int k=i;k<j;k++){
		dfs(i,k);
		dfs(k+1,j);
		dps[i][j]=min(dps[i][j],dps[i][k]+dps[k+1][j]);
	}
	cal[i][j]=true;
}
int main()
{
	scanf("%s",que);
	len=strlen(que);
	memset(cal,false,sizeof(cal));
	memset(dps,0x7f,sizeof(dps));
	dfs(0,len-1);
	printf("%d
",dps[0][len-1]);
	return 0;
}