NYOJ  15 括号匹配

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

输入

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

输出

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

样例输入

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

样例输出

0
0
3
2

去年暑假，就在思考这个问题，今天终于解决了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 102
#define INF 1e9
int result[N][N];//保存从i 到 j所需要的最少括号数
char s[N];
int Min(int i,int j)
{if(result[i][j]!=INF)return result[i][j];else{for(int t=i;t<j;t++){int tempa=Min(i,t);int tempb=Min(t+1,j);//如果第i 和 第j 匹配的话，那么result[i][j]=result[i+1][j-1]if(s[i-1]=='('&&s[j-1]==')'||(s[i-1]=='['&&s[j-1]==']'))result[i][j]=min(result[i][j],result[i+1][j-1]);result[i][j]=min(result[i][j],tempa+tempb);}return result[i][j];}
}
int main()
{int n,T,i,j;cin>>T;while(T--){scanf("%s",s);n=strlen(s);for(i=1;i<=n;i++)for(j=i+1;j<=n;j++){result[i][j]=INF;}result[n][n]=1;for(i=1;i<n;i++){result[i][i]=1;result[i+1][i]=0;}cout<<Min(1,n)<<endl;/*  cout<<"************"<<endl;for(i=1;i<=n;i++){for(j=1;j<=n;j++){cout<<result[i][j]<<" ";}cout<<endl;}*/}return 0;
}