Brackets（区间dp）

#include<iostream>
#include<string.h>
using namespace std;
int dp[109][109];


int main(){
	string a;
	while(cin>>a){
	
	if(a=="end") break;
	int n=a.size();
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n-1;i++){
		if(a[i]=='('&&a[i+1]==')'||a[i]=='['&&a[i+1]==']'){
			dp[i][i+1]=2;
		}
//		printf("dp[%d][%d]:%d \n",i,i+1,dp[i][i+1]);
	}
	for(int len=2;len<n;len++){
		for(int l=0;l+len<n;l++){
			int r=l+len;
			if(a[l]=='('&&a[r]==')'||a[l]=='['&&a[r]==']') dp[l][r]=dp[l+1][r-1]+2;
			for(int k=l;k<r;k++){
				dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);
	//			printf("dp[%d][%d]:%d    len:%d   k:%d \n",l,r,dp[l][r],len,k);
			}
		}
	}
	cout<<dp[0][n-1]<<endl;
	}
}