NYOJ 15 括号匹配（二）

#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;
}