题目描述：给出一串由‘（‘）’‘ [ ' ' ] '组成的串，让你输出添加最少括号之后使得括号匹配的串。
像([)] 这样都是不合法的，所以不可能贪心去做。
设d[i][j]为子串s(i,j)至少添加几个括号，所以，当s[i]==s[j]时，有d[i][j]=d[i+1][j-1],设pos[i][j]为-1，不同时，可以分成两部分，转移到d[i][k]和d[k+1][j]，用pos[i][j]记录下转移时候的下标，边界条件就是d[i][i]时为1，因为只有一个字符，还有一点是d[i+1][i]初值为0，如"[]"时，转移时会出现这样的下标，其他的初始化值就设一个极大值，就是字符串长度了
最后递归打印，格式需要注意一下，各个答案间隔一行，最后一个答案不需要输出空格。
#include <iostream> #include <cstdio> #include <ctime> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <set> #include <queue> using namespace std; typedef unsigned long long ll; const int INF=1e9+100; const int mod=1e9+7; int d[105][105],pos[105][105]; char s[105]; void print(int l,int r){ if(l>r) return; if(l==r){ if(s[l]=='('||s[l]==')') printf("()"); else printf("[]"); return; } if(pos[l][r]==-1){ printf("%c",s[l]); print(l+1,r-1); printf("%c",s[r]); }else{ print(l,pos[l][r]); print(pos[l][r]+1,r); } } int main(){ //freopen("out.txt","w",stdout); int n,T; scanf("%d",&T); getchar(); while(T--){ gets(s+1); gets(s+1); int len=strlen(s+1); for(int j=1;j<=len;j++){ d[j][j]=1; d[j+1][j]=0; } for(int i=len;i>=1;i--) for(int j=i+1;j<=len;j++){ d[i][j]=len; if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){ d[i][j]=min(d[i][j],d[i+1][j-1]); pos[i][j]=-1; } for(int k=i;k<j;k++){ if(d[i][j]>=d[i][k]+d[k+1][j]){ d[i][j]=d[i][k]+d[k+1][j]; pos[i][j]=k; } } } print(1,len); printf("\n"); if(T) printf("\n"); } return 0; }