南阳理工OJ 15 括号匹配（二）动态规划

连接： http://acm.nyist.net/JudgeOnline/problem.php?pid=15

括号匹配（二）

时间限制：1000 ms  |  内存限制：65535 KB

难度：6

 

描述

给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的

 

输入

第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100

输出

对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行

样例输入

4
[]
([])[]
((]
([)]

样例输出

0
0
3
2

 

 

 

#include<stdio.h>
#include<string.h>
int result[110][110];
char str[110];
bool p(char x,char y)
{
	return(x=='('&&y==')'||x=='['&&y==']');
}
int dp(int x=0,int y=strlen(str))//一般都用左闭右开区间
{
	if(x==y)
	{
		result[x][y]=0;//这句话不要忘记
		return(0);
	}
	int i,f=0,min=1000;
	for(i=x+1;i<y;i++)
	{
		if(p(str[x],str[i]))
		{
			if(result[x+1][i]==-1)result[x+1][i]=dp(x+1,i);
			if(result[i+1][y]==-1)result[i+1][y]=dp(i+1,y);
			result[x][y]=result[x+1][i]+result[i+1][y];
			if(min>result[x][y])min=result[x][y];
			f=1;
		}
	}
	result[x][y]=min;
	if(f==0)result[x][y]=1+dp(x+1,y);
	return(result[x][y]);
}
int main()
{
//	freopen("in.txt","r",stdin);  //这句话不要忘记去掉
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(result,-1,sizeof(result));
		scanf("%s",str);
		printf("%d\n",dp());
	}
	return(0);
}