http://acm.pku.edu.cn/JudgeOnline/problem?id=1141根据刘汝佳的推荐，这道题是“简单”的动态规划，却用了我两个多小时的时间……
还是不熟悉啊 ，呵呵 时间主要浪费在第一个思路上。
两个思路；
思路一：
int num[i][j]表示第i个字符到第j个字符需要添加的最少字符数。string after[i][j]表示操作后，第i个字符到第j个字符按照最优方案添加括号后的串。
输出after[0][len-1]
#include"stdio.h"
#include"string.h"
char *after[100][100];
int num[100][100];
char *str=new char[100];
int len;
char * str_bin(char* str1, char* str2) //合并字符串的函数
{
int n = strlen(str1)+strlen(str2);
char* str = new char[n+1];
int i = 0;
while ( *str1 && *str2)
{
if (*str1 < *str2)
str[i++] = *str1++;
else
str[i++] = *str2++;
}
if (*str1)
while (str[i++] = *str1++);
else
while (str[i++] = *str2++);
return str;
}
void dp()
{
int i,j,k,z;
for(i=len-1;i>=0;i--)
for(j=i;j<=len-1;j++)
{
num[i][j]=32767;
after[i][j]=new char[100];
after[i][j]="";
} //初始化
for(i=len-1;i>=0;i--)
for(j=i;j<=len-1;j++)
{
if(i==j)
{
num[i][j]=1;
if(str[i]=='(') after[i][j]="()";
if(str[i]==')') after[i][j]="()";
if(str[i]=='[') after[i][j]="[]";
if(str[i]==']') after[i][j]="[]";
}
else
{
if(str[i]=='('&&str[j]==')')
if(num[i+1][j-1]<num[i][j])
{
num[i][j]=num[i+1][j-1];
after[i][j]='('+after[i+1][j-1]+')';
}
else if(str[i]=='['&&str[j]==']')
if(num[i+1][j-1]<num[i][j])
{
num[i][j]=num[i+1][j-1];
after[i][j]='['+after[i+1][j-1]+']';
}
for(k=i;k<j;k++)
if(num[i][k]+num[k+1][j]<num[i][j])
// if(strlen(after[i][j])>strlen(after[i][k])+strlen(after[k+1][j]) )
{
num[i][j]=num[i][k]+num[k+1][j];
after[i][j]=str_bin(after[i][k],after[k+1][j]);
}
}
}
}
void main()
{
while (scanf("%s", str) != EOF)
{
len=strlen(str);
dp();
printf("%s\n",after[0][len-1]);
}
}总是WA,连Sample Input里的数据都通不过。而且我char *after[][]是三维数组，太不方便了，代码看起来很乱,很不爽。
想起学C语言时候，判断括号匹配时用的是递归。那能不能在查找匹配时也用递归呢? 于是有了思路二。
思路二：
int opt[i,j]表示第i个字符到第j个字符需要添加的最少字符数，状态转移方程： a[i,j]=min(a[i,k]+a[k+1,j])
#include "string.h"
#include "stdio.h"
char str[128];
int opt[110][110],tag[110][110]; //tag记录能否str[st]和str[end]中划分子问题，用opt[i][j]表示从str[st]到str[end]所需要插入的最小字符数
void search(int st,int end)
{
if(st>end) return;
else if(st==end){ //如果剩下最后一个字符，为之配对
if(str[st]=='('||str[st]==')')
printf("()");
else printf("[]");
}
else{
if(tag[st][end]==-1){ //如果str[st]和str[end]配对（tag==-1），打印str[st]和str[end],继续搜索str[st+1]和str[end-1]
if(str[st]=='('){
printf("(");
search(st+1,end-1);
printf(")");
}else{
printf("[");
search(st+1,end-1);
printf("]");
}
}
else{ //如果str[st]和str[end]不配对（tag!=-1），搜索从tag分开的两个子问题
search(st,tag[st][end]);
search(tag[st][end]+1,end);
}
}
}
void main()
{
int len,i,interval,j,k,s,tmp;
while(scanf("%s",str)!=EOF)
{
len=strlen(str);
for(i=0;i<len;i++)opt[i][i]=1; //初始化，
for(interval=1;interval<len;interval++) //从间隔1个字母到间隔len-1个字母分别计算tag
for(i=0;i+interval<len;i++)
{
j=i+interval;
tmp=32767;
if(str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']') //如果str[i]和str[j]可以配对，问题转化为求str[i+1][j-1]的tag
tmp=opt[i+1][j-1];
tag[i][j]=-1;
for(k=i;k<j;k++)
{
if(tmp>opt[i][k]+opt[k+1][j])
{
tmp=opt[i][k]+opt[k+1][j];
tag[i][j]=k;
}
opt[i][j]=tmp;
}
}
search(0,len-1);
printf("\n");
}
return;
}