括号匹配（二）
时间限制：1000 ms | 内存限制：65535 KB
难度：6
描述给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如：[]是匹配的([])[]是匹配的((]是不匹配的([)]是不匹配的
输入
第一行输入一个正整数N，表示测试数据组数(N<=10)每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100
输出
对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行
样例输入
4
[]
([])[]
((]
([)]
样例输出
0 0 3 2
思路：这是一个区间动态规划问题，和《计算机算法设计与分析》中的矩阵连成是一个类型。类比着就可以写出来。 一个字符串，长度假设为n;如果要求从第1位到第n位中的最少括号添加个数dp[1][n]；如果第一位和最后一位可以匹配，就可以将这两位给忽略掉，这个时候就成为了求dp[1+1][n-1]；如果起始位和末尾位不能匹配，那么必定存在一个分界位第k位，使得从第1位到第k位所需要加的最少括号数量dp[1][k]和第k+1位到第n位所需要加的括号数量dp[k+1][n]相加起来的和能够凑成整个问题的最优值。 当子问题划分到最小，也就是只有一位的时候，所需要加的位数是1，也就是说一个"("需要一个")"来将其匹配。所以dp[i][i]=1;AC代码如下：
#include
#include
#include
#include
using namespace std;
//static int MAX_LEN=105;
int dp[105][105];
int isPP(char a,char b)
{
if(a=='('&&b==')'||(a=='['&&b==']'))
return 1;
else
return 0;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
string str;
//scanf("%s",&str);
cin>>str;
memset(dp,0,sizeof(dp));
for(int i=0;i { dp[i][i]=1; } for(int len=1;len { for(int i=0;i { int j=i+len; dp[i][j]=10000; if(isPP(str[i],str[j])) dp[i][j]=dp[i][j] for(int k=i;k dp[i][j]=dp[i][j]<(dp[i][k]+dp[k+1][j])?dp[i][j]:(dp[i][k]+dp[k+1][j]); } } printf("%d\n",dp[0][str.length()-1]); } system("pause"); return 0; } 2014-05-0421:44:22