nyoj 括号匹配（二） 15 （区间dp） 好题

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MIN(a,b) (a>b?b:a)
int dp[1100][1100];
char a[1100];
int main()
{
	int t,i,j,k,l,ii;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		scanf("%s",a);
		l=strlen(a);
		for(i=0;i<l;i++)
		{
			for(j=0;j<l;j++)
			{
				if(i<j)
					dp[i][j]=110;
				else if(i==j)
					dp[i][i]=1;
				else 
					dp[i][j]=0;
			}
		}
		for(ii=1;ii<l;ii++)//表示区间，从一一直到l,全部遍历 
		{
			for(i=0;i<l-1;i++)
			{
				j=ii+i;
				if((a[i]==(&&a[j]==))||(a[i]==[&&a[j]==]))
					dp[i][j]=MIN(dp[i][j],dp[i+1][j-1]);
				for(k=i;k<j;k++)
					dp[i][j]=MIN(dp[i][j],dp[i][k]+dp[k+1][j]);
			}
		}
		printf("%d\n",dp[0][l-1]);
	}
	return 0;
}