我觉得这一份代码和题解和紫书上的也差不了多少啊...
这样写的复杂度难道不应该是 $O(n^2)$ 的吗...
可为啥这个提交上去就超时呢...
求大佬看一眼

#include <cstdio>
#include <cstring>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 100 + 10;
int dp[maxn][maxn], n;
char str[maxn];

void print(int, int);
bool check(int i, int k) { return (str[i] == '[' && str[k] == ']') || (str[i] == '(' && str[k] == ')'); }

int main()
{
	int t;	scanf("%d", &t);
	while (getchar() != '\n')
		;
	while (getchar() != '\n')
		;
	while (t--)
	{
		str[1] = '\0';
		fgets(str + 1, maxn - 2, stdin);
//		scanf("%[^\n]", str + 1);
//		while (getchar() != '\n')
//			;
		while (getchar() != '\n')
			;
		n = strlen(str + 1);
		str[n--] = '\0';
		if (!n)
		{
			puts("\n");
			continue;
		}
		for (int i = 1;i <= n;i++)
			dp[i][i] = 1, dp[i + 1][i] = 0;
		for (int t = 1;t <= n - 1;t++)
			for (int i = 1;i + t <= n;i++)
			{
				dp[i][i + t] = n;
				if (check(i, i + t))
					dp[i][i + t] = min(dp[i][i + t], dp[i + 1][i + t - 1]);
				dp[i][i + t] = min(dp[i][i + t], dp[i + 1][i + t] + 1);
				dp[i][i + t] = min(dp[i][i + t], dp[i][i + t - 1] + 1);
			}
		print(1, n);
		puts("");
		if (t)
			puts("");
	}
}

void print(int i, int k)
{
	if (i == k)
	{
		if (str[i] == '(' || str[i] == ')')
			printf("()");
		else //if (str[i] == '[' || str[i] == ']')
			printf("[]");
		return;
	}
	if (i > k)
		return;
	if (!dp[i][k])
	{
		for (;i != k + 1;i++)
			putchar(str[i]);
		return;
	}
	if (check(i, k) && dp[i][k] == dp[i + 1][k - 1])
	{
		putchar(str[i]);
		print(i + 1, k - 1);
		putchar(str[k]);
		return;
	}
	for (int x = i;x < k;x++)
		if (dp[i][x] + dp[x + 1][k] == dp[i][k])
		{
			print(i, x);	print(x + 1, k);
			return;;
		}
}