括号匹配（二）

时间限制：

1000 ms  |  内存限制：

65535 KB

难度：

6

描述

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

如：

[]是匹配的

([])[]是匹配的

((]是不匹配的

([)]是不匹配的

输入

第一行输入一个正整数N，表示测试数据组数(N<=10)

每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100

输出

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

样例输入

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

样例输出

0032 分析题目： 用 dp[j][i] 表示从位置 j 到字符位置 i 所需的最少括号数(i > j），那么这一状态可由下面得到： 1.如果 第j个字符到第i - 1个字符中没有与第i个字符匹配的括号，则所需的括号数加1，         即：f[j][i] = f[j][i - 1] + 1； 2.如果 k=j 时正好匹配则  因为dp[j][j-1]=0，这就是第一次匹配（注意可能存在多个字符与之匹配，即可能存在多个k） ;                          即：dp[j][i]=min(dp[j][i],dp[k+1][i-1])； 3.如果 第k（j < k < i）个字符再次与第i个字符匹配，那么所需括号数为第j到第k - 1个字符所需字符数加上第k + 1个字符到第i - 1个字符  ，所需括号数为         即：dp[j][i] = min(dp[j][i], dp[j][k - 1] + dp[k + 1][i - 1])。   例如：这种情况 [ ) ) [ ( ( [ ) ) ] 当 i 为 len-1 时               1     2     3                     1为第一次匹配，2为第二次匹配。。。 AC代码一：

1 //第二种情况，和第三种合并为了一种，因为dp[j][j-1]=0; 2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6 bool f(char a,char b) 7 { 8     if(a=='('&&b==')') 9         return 1;10     if(a=='['&&b==']')11         return 1;12     return 0;13 }14 int dp[200][200];15 int main()16 {17     int n ;18     cin>>n;19     while(n--)20     {21         string s;22         cin >> s;23         int len = s.length();24         memset(dp,0,sizeof(dp));25         for(int i = 0 ; i <= len ; i++)26             dp[i][i]=1;27         for(int i = 1 ; i < len ; i++){28             for(int j = i-1 ; j >= 0; j--)29             {30                 dp[j][i] = dp[j][i-1] + 1;31                 for(int k = j ; k < i ; ++ k)32                 {33                     if(f(s[k],s[i]))//当k=j时，为第一次与s[i]匹配；34                     {35                         dp[j][i]=min(dp[j][i],dp[j][k-1]+dp[k+1][i-1]);36                     }37                 }38             }39         }40         printf("%d\n",dp[0][len-1]);41     }42     return 0;43 }
          
         
        

  AC代码二：

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 using namespace std; 6 #define N 101 7 #define MAX 0xfffffff 8 int dp[N][N]; 9 int min(int a,int b)10 {11 return a
            >a;21          len = strlen(a);22     memset(dp,0,sizeof(dp));23     for(i=0;i