括号匹配（二）
时间限制：1000 ms | 内存限制：65535 KB
难度：6
- 描述
- 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的- 输入
- 第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100 - 输出
- 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行
- 样例输入
-
4 [] ([])[] ((] ([)]
- 样例输出
-
0 0 3 2
主要思想就是将原问题化成子问题。
设dp[i][j]为第i个位置到第j个位置需要添加的符号数。设待判断字符串为s。
从i开始寻找与s[j]相等的字符，位置设为k，即s[k]==s[j]，i<=k<j。
当找到时，dp[i][j]即为dp[i][j]和dp[i][k-1]+dp[k+1][j-1]中的小值。如果找不着，dp[i][j]=dp[i][j-1]+1。
动态规划是将原问题转化成子问题，但是解的时候还是从底往上的，所以还是从i==j开始的。
当i==j的时候，dp[i][j]=1。
01.#include
<iostream>02.#include
<string>03.#include
<string.h>04.#include
<cmath>05.using namespace std;06. 07.#define
maxN 10208. 09.int dp[maxN][maxN];10. 11.bool Match(char a,char b)12.{13.if((a=='('&&b==')')||(a=='['&&b==']'))14.return true;15.return false;16.}17. 18.int main()19.{20.int t;21.cin>>t;22.while(t--)23.{24.memset(dp,0,sizeof(dp));25.string
s;26.cin>>s;27.int len=s.size();28.for(int i=0;i<len;i++)29.dp[i][i]=1;30.for(int j=1;j<len;j++)31.{32.for(int i=0;i<j;i++)33.{34.dp[i][j]=dp[i][j-1]+1;35.for(int k=i;k<j;k++)36.{37.if(Match(s[k],s[j]))38.{39.dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j-1]);40.}41.}42.}43.}44.cout<<dp[0][len-1]<<endl;45.}46.}
如上面所说，既然可以将问题转化成子问题，那这样也就可以用递归来做了。
01.#include
<iostream>02.#include
<string>03.#include
<string.h>04.#include
<cmath>05.using namespace std;06. 07.#define
maxN 10208. 09.int a[maxN][maxN];10. 11.int Recur(string
&s,int left,int right)12.{13.if(a[left][right]>=0)return a[left][right];14.if(left==right)15.return a[left][right]=1;16.if(left>right)17.return 0;18.int tmp=maxN;19.if((s[left]=='('&&s[right]==')')||(s[left]=='['&&s[right]==']'))20.tmp=Recur(s,left+1,right-1);21.for(int k=left+1;k<right;k++)22.{23.if((s[k]=='('&&s[right]==')')||(s[k]=='['&&s[right]==']'))24.{25.tmp=min(tmp,Recur(s,left,k-1)+Recur(s,k+1,right-1));26.}27.}28.if(tmp==maxN)29.tmp=Recur(s,left,right-1)+1;30.return a[left][right]=tmp;31.}32. 33.int main()34.{35.int t;36.cin>>t;37.while(t--)38.{39.string
s;40.cin>>s;41.memset(a,-1,sizeof(a));42.cout<<Recur(s,0,s.size()-1)<<endl;43.}44.return 0;45.}
参考：http://blog.csdn.net/hearthougan/article/details/23111951