链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4501
题意：
定义如下正规括号序列（字符串）：
1.空序列是正规括号序列。
2.如果S是正规括号序列，那么(S)和[S]也是正规括号序列。
3.如果A和B都是正规括号序列，那么AB也是正规括号序列。
输入一个长度不超过100的，由“(”、“)”、“[”、“]”构成的序列，添加尽量少的括号，得到一个正规序列。
如有多解，输出任意一个序列即可。
分析：
设串S至少需要增加d(S)个括号，转移如下：
1.如果S形如(S′)或者[S′]，转移到d(S′)。
2.如果S至少有两个字符，则可以分成AB，转移到d(A)＋d(B)。
边界是：S为空时d(S)=0，S为单字符时d(S)=1。
注意：不管S是否满足第一种，都要尝试第二种转移，否则“[][]”会转移到“][”，然后就只能加两个括号了。
设d(i,j)表示子串S[i～j]至少需要添加几个括号。
对于第一种，状态转移方程为：d(i,j) = d(i+1, j-1)。
对于第二种，状态转移方程为：d(i,j) = min{d(i, k) + d(k+1, j) | i ≤ k < j}。
可以在打印解的时候重新检查一下哪个决策最好。
最后，这题的输入输出有点坑。。。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int UP = + ;
char s[UP];
int d[UP][UP]; // d[L][R]表示子串s[L～R]至少需要添加几个括号 bool match(char L, char R){
return (L == '(' && R == ')') || (L == '[' && R == ']');
} void dynamic_programming(int len){
for(int i = ; i < len; i++){
d[i][i] = ;
d[i+][i] = ;
}
for(int L = len - ; L >= ; L--){
for(int R = L + ; R < len; R++){
int& v = d[L][R];
v = match(s[L], s[R]) ? d[L+][R-] : ;
for(int M = L; M < R; M++) v = min(v, d[L][M] + d[M+][R]);
}
}
} void output(int L, int R){
if(L > R) return;
if(L == R){
if(s[L] == '(' || s[L] == ')') printf("()");
else printf("[]");
return;
}
int ans = d[L][R];
if(match(s[L], s[R]) && d[L+][R-] == ans){
printf("%c", s[L]); output(L+, R-); printf("%c", s[R]);
return;
}
for(int M = L; M < R; M++) if(d[L][M] + d[M+][R] == ans){
output(L, M); output(M+, R);
return;
}
} int main(){
int T;
scanf("%d", &T);
getchar();
while(T--){
gets(s); gets(s);
int len = strlen(s);
dynamic_programming(len);
output(, len - ); printf("\n");
if(T) printf("\n");
}
return ;
}
最后，再贴一下我一开始的代码，状态的转移有点不同：当s[L]与s[M]不匹配时，d(L,M)转移到d(L+1,M)+1。
递推写法：
#include <cstdio>
#include <cstring> const int UP = + ;
char s[UP];
int d[UP][UP], ans[UP][UP]; int diff(int L, int R){
if(s[L] == '(') return s[R] != ')';
if(s[L] == '[') return s[R] != ']';
return ;
} void dynamic_programming(int len){
for(int i = ; i < len; i++){
d[i][i] = ;
d[i+][i] = ;
}
for(int L = len - ; L >= ; L--){
for(int R = L + ; R < len; R++){
d[L][R] = ;
for(int M = L; M <= R; M++){
int f = diff(L, M);
int v = f + d[L+][M-+f] + d[M+][R];
if(d[L][R] > v){
d[L][R] = v;
ans[L][R] = M;
}
}
}
}
} void output(int L, int R){
if(L > R) return;
if(L == R){
if(s[L] == '(' || s[L] == ')') printf("()");
else printf("[]");
return;
}
int M = ans[L][R];
if(L == M){
output(L, M); output(M+, R);
return;
}
printf("%c", s[L]);
if(!diff(L, M)) output(L+, M-), printf("%c", s[M]);
else output(L+, M), printf("%c", s[L] == '(' ? ')' : ']');
output(M+, R);
} int main(){
int T;
scanf("%d", &T);
getchar();
while(T--){
gets(s); gets(s);
int len = strlen(s);
dynamic_programming(len);
output(, len - ); printf("\n");
if(T) printf("\n");
}
return ;
}
记忆化写法（比递推写法慢几倍）：
#include <cstdio>
#include <cstring> const int INF = 0x3f3f3f3f;
const int UP = + ;
int d[UP][UP], ans[UP][UP];
char s[UP]; int diff(int L, int R){
if(s[L] == '(') return s[R] != ')';
if(s[L] == '[') return s[R] != ']';
return ;
} int dp(int L, int R){
if(L > R) return ;
if(L == R) return ;
int& v = d[L][R];
if(v != INF) return v; for(int M = L; M <= R; M++){
int f = diff(L, M);
int res = f + dp(L+, M-+f) + dp(M+, R);
if(v > res){
v = res;
ans[L][R] = M;
}
}
return v;
} void output(int L, int R){
if(L > R) return;
if(L == R){
if(s[L] == '(' || s[L] == ')') printf("()");
else printf("[]");
return;
}
int M = ans[L][R];
if(L == M){
output(L, M); output(M+, R);
return;
}
printf("%c", s[L]);
if(!diff(L, M)) output(L+, M-), printf("%c", s[M]);
else output(L+, M), printf("%c", s[L] == '(' ? ')' : ']');
output(M+, R);
} int main(){
int T;
scanf("%d", &T);
getchar();
while(T--){
gets(s); gets(s);
memset(d, INF, sizeof(d));
dp(, strlen(s) - );
output(, strlen(s) - );
printf("\n");
if(T) printf("\n");
}
return ;
}