状态表示：d(i,j) 表示 i~j至少要添加几个括号
状态转移：1）(S) 或 [S] 转移成 S ，即d(i,j) --> d(i+1,j-1) 如果 s[i]==s[j]
2） A=S1+S2 转移成 S1和S2 ，即 d(i,j0 --> d(i,k)+d(k+1,j)
但每种都要转移到第二种方法试一试 ，如[][]只是第一种会导致到 ][ 状态去了
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=100+5;
int d[maxn][maxn],N;
char s[maxn];
//d(i,j) 表示i~j 要添加的括号数
bool match(char a,char b){ return (a=='['&&b==']')||(a=='('&&b==')'); }
void dp()
{for(int i=0;i<N;i++)d[i+1][i]=0,d[i][i]=1; //只有一个字符只要补上另一个就好 for(int i=N-2;i>=0;i--)for(int j=i+1;j<N;j++){d[i][j]=N;if(match(s[i],s[j])) //第一种状态转移 d[i][j]=min(d[i][j],d[i+1][j-1]);for(int k=i;k<j;k++) //第二种状态转移 d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);}}
void print_ans(int i,int j)
{if(i>j) return; if(i==j) //就一个字符的话直接补上 {if(s[i]=='('||s[i]==')') printf("()");else printf("[]");return ;}int ans=d[i][j];if(match(s[i],s[j])&&ans==d[i+1][j-1]){ //第一种状态转移printf("%c",s[i]);print_ans(i+1,j-1);printf("%c",s[j]);return ;}for(int k=i;k<j;k++)if(ans==d[i][k]+d[k+1][j]){ //第二种状态转移print_ans(i,k);print_ans(k+1,j);return ;}}
int main()
{int n;fgets(s,maxn,stdin);sscanf(s,"%d",&n);fgets(s,maxn,stdin);while(n--){fgets(s,maxn,stdin);memset(d,-1,sizeof(d)); N=strlen(s)-1;dp();print_ans(0,N-1);cout<<endl;if(n) cout<<endl;fgets(s,maxn,stdin);}return 0;
}