首页 > 代码库 > NYOJ 15 括号匹配（二）

NYOJ 15 括号匹配（二）

2024-07-15 10:02:16   221人阅读

括号匹配（二）

时间限制：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;
}


联系
我们