括号匹配（二）
时间限制：1000 ms | 内存限制：65535 KB
难度：6
- 描述
- 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的
- 输入
- 第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100 - 输出
- 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行
- 样例输入
-
4
[]
([])[]
((]
([)] - 样例输出
-
0
0
3
2
分析题目：
用 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代码一：//第二种情况，和第三种合并为了一种，因为dp[j][j-1]=0;
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
bool f(char a,char b)
{
if(a=='('&&b==')')
return ;
if(a=='['&&b==']')
return ;
return ;
}
int dp[][];
int main()
{
int n ;
cin>>n;
while(n--)
{
string s;
cin >> s;
int len = s.length();
memset(dp,,sizeof(dp));
for(int i = ; i <= len ; i++)
dp[i][i]=;
for(int i = ; i < len ; i++){
for(int j = i- ; j >= ; j--)
{
dp[j][i] = dp[j][i-] + ;
for(int k = j ; k < i ; ++ k)
{
if(f(s[k],s[i]))//当k=j时，为第一次与s[i]匹配；
{
dp[j][i]=min(dp[j][i],dp[j][k-]+dp[k+][i-]);
}
}
}
}
printf("%d\n",dp[][len-]);
}
return ;
}AC代码二：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
#define N 101
#define MAX 0xfffffff
int dp[N][N];
int min(int a,int b)
{
return a<b ? a:b;
}
int main()
{
int t,len,i,j,l,k,mmin,s;
char a[N];
scanf("%d",&t);
while(t--)
{
cin>>a;
len = strlen(a);
memset(dp,,sizeof(dp));
for(i=;i<len;i++)
dp[i][i]=; //一个括号需要加一个括号才能被匹配成功
for(i=;i<len;i++)
for(j=;j<len-i;j++)
{
k=j+i; mmin=MAX;
dp[j][k]=MAX;
if( ( a[j]=='(' && a[k]==')' ) || ( a[j]=='['&&a[k]==']' ) ) //如果匹配，则无需添加括号
dp[j][k]=dp[j+][k-];
//局部最小
for(l=j;l<=k;l++) //如果不需要，就找到添加的位置
{
mmin = min(mmin,dp[j][l]+dp[l+][k]);
}
//整体最小
dp[j][k]=min(dp[j][k],mmin);
}
printf("%d\n",dp[][len-]);
}
return ;
}