NYOJ-括号匹配（二）-动态规划

括号匹配（二）

时间限制：1000 ms  |  内存限制：65535 KB难度：6

描述

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

输入

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

输出

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

样例输入

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

样例输出

0
0
3
2

AC代码

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
bool isMatch(char a,char b)
{
    if(((a == '(' && b == ')') || (a == '[' && b == ']')))
        return true;
    else
        return false;
}
int main()
{
    int n;
    scanf("%d",&n);
    int dp[105][105];//表示从i到j的匹配括号数量最小值
    while(n--)
    {
        getchar();
        char ch[105];
        scanf("%s",ch+1);
        int len1=strlen(ch+1);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=len1;i++)
            dp[i][i]=1;
         //结果为两种，一种是在不同位置的匹配后结果取最小，一种是不匹配结果取最小
        for(int j=1;j<=len1;j++)
        {
            for(int i=j-1;i>=1;i--)
            {
                int tmp=0x3f3f3f;//定义一个最大值
                for(int k=i+1;k<=j;k++)
                {
                    //i、j、k的位置关系是1<=i<k<=j<=len1
                    if(isMatch(ch[i],ch[k]))//能够匹配
                    {
                        tmp=min(tmp,dp[i+1][k-1]+dp[k+1][j]);
                    }
                }
                dp[i][j]=min(tmp,dp[i+1][j]+1);
            }
        }
        printf("%d\n",dp[1][len1]);
    }
    return 0;
}