题目大意
给你一个括号串（包括'('，')'，'['，']'），长度不超过 100，问你怎么添加最少的括号，使得这个括号串是合法的，输出添加括号后的合法括号串
做法分析
以长度划分阶段，定义状态：f[i][j] 表示，s(i)~s(j) 这一个字串需要添加多少括号使得其变为合法字串，状态转移：
f[i][j]=min{ f[i][k]+f[k+1][j] }
有一个特殊的地方就是：s(i) 和 s(j) 是两个匹配的括号，即：s(i)=='(' && s(j)==')' || s(i)=='[' && s[j]==']'，那么 f[i][j] 还要和 f[i+1][j-1] 相比取最小者
最后输出的时候，递归的输出就行
这是今天无意间翻到的，不知道是什么时候看见了没有想法的一道题，没想到今天瞬间就把思路给秒了...这么水的DP，当时怎么会没想法呢？
参考代码
POJ 1141
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std; 6 7 const int N=106; 8 9 char buff[N]; 10 int f[N][N], pre[N][N]; 11 12 void Print(int L, int R) 13 { 14 if(L>R) return; 15 if(L==R) 16 { 17 if(buff[L]=='[' || buff[L]==']') printf("[]"); 18 else printf("()"); 19 } 20 else if(pre[L][R]==-1) 21 { 22 printf("%c", buff[L]); 23 Print(L+1, R-1); 24 printf("%c", buff[R]); 25 } 26 else Print(L, pre[L][R]), Print(pre[L][R]+1, R); 27 } 28 29 int main() 30 { 31 while(gets(buff)) 32 { 33 int n=(int)strlen(buff); 34 memset(f, 0, sizeof f); 35 for(int i=0; i<n; i++) f[i][i]=1, pre[i][i]=0; 36 for(int len=2; len<=n; len++) 37 { 38 for(int i=0; i+len-1<n; i++) 39 { 40 int j=i+len-1; 41 f[i][j]=0x3ffffff; 42 if(buff[i]=='[' && buff[j]==']' || buff[i]=='(' && buff[j]==')') 43 f[i][j]=f[i+1][j-1], pre[i][j]=-1; 44 for(int k=i; k<j; k++) 45 if(f[i][j]>f[i][k]+f[k+1][j]) 46 f[i][j]=f[i][k]+f[k+1][j], pre[i][j]=k; 47 } 48 } 49 Print(0, n-1), printf("\n"); 50 } 51 return 0; 52 }