括号匹配（二）
时间限制：1000 ms | 内存限制：65535 KB
难度：6
- 描述
- 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的- 输入
- 第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100 - 输出
- 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行
- 样例输入
-
4 [] ([])[] ((] ([)]
- 样例输出
-
0 0 3 2
分析：dp[i][j]——从i到j需要添加的括号数，枚举i到j距离m( 1 ~ (len-1) )
当s[i]和s[j]匹配时： dp[i][j]=min( dp[i][j] ,dp[i+1][j-1] ) , dp[i][j]=min( dp[i][j], dp[i][k]+dp[k+1][j] )
代码：
#include <stdio.h>
#include <string.h>
int min(int x, int y)
{
if (x > y) return y;
return x;
}
int dp[150][150];
int main()
{
int n, m, i, j, k;
char s[101];
scanf("%d", &n);
while (n--)
{
scanf("%s", s);
int len = strlen(s);
memset(dp, 0, sizeof(dp));
for (i = 0; i < len; i++)
dp[i][i] = 1; // 一个字符匹配数为1
for (m = 1; m < len; m++)
{
for (i = 0; i < len - m; i++)
{
j = i + m;
dp[i][j] = 150;
if ((s[i] == '('&&s[j] == ')') || (s[i] == '['&&s[j] == ']'))
dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
for (k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
printf("%d\n", dp[0][len - 1]);
}
return 0;
}