南阳理工OJ -- 15 括号匹配

描述

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

输入

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

输出

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

样例输入

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

样例输出

0
0
3
2

思路：动态规划，设dp[i][j]表示第i个字符到第j个字符所需要的最少匹配数，则：（1），如果从第i到j-1个字符中没有一个与第j个字符匹配，那么状态转移方程为 dp[i][j] = dp[i][j-1] + 1 (2)，如果在第i到j-1字符中存在与第j个字符匹配的字符（记为k,且把所有满足条件的k组成的集合记为A）那么状态转移方程为 dp[i][j] = min(dp[i][j],dp[i][k-1] + dp[k+1][j-1]) （k属于集合A）。

 1 #include<iostream>
 2 #include<string>
 3 #define MAXN 111
 4 using namespace std;
 5 int dp[MAXN][MAXN];
 6 string str;
 7 int main(){
 8     int t;
 9     cin >> t;
10     while(t--){
11         str.clear();
12         cin >> str;
13         for(int i = 0;i < str.size();i ++) dp[i][i] = 1;
14         for(int i = 1;i < str.size();i ++){
15             for(int j = i-1;j >= 0;j --){
16                 dp[j][i] = dp[j][i-1] + 1;
17                 for(int k = j;k < i;k ++){
18                     if(str[k] - str[i] == -1 || str[k] - str[i] == -2)
19                         dp[j][i] = min(dp[j][i], dp[j][k-1] + dp[k+1][i-1]);
20                 }
21             }
22         }
23         cout << dp[0][str.size()-1] << endl;
24     }
25     return 0;
26 }

 

南阳理工OJ -- 15 括号匹配,布布扣,bubuko.com

南阳理工OJ -- 15 括号匹配

原文：http://www.cnblogs.com/anhuizhiye/p/3658384.html