NYOJ 15 括号匹配（二） - c++编程基础

括号匹配（二）

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

描述

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

输入

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

输出

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

样例输入

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

样例输出

分析：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 
      
       
#include 
       
         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; }