http://acm.pku.edu.cn/JudgeOnline/problem?id=1141根據(jù)劉汝佳的推薦，這道題是“簡單”的動態(tài)規(guī)劃，卻用了我兩個(gè)多小時(shí)的時(shí)間……
還是不熟悉啊 ，呵呵 時(shí)間主要浪費(fèi)在第一個(gè)思路上。
兩個(gè)思路；
思路一：
int num[i][j]表示第i個(gè)字符到第j個(gè)字符需要添加的最少字符數(shù)。string after[i][j]表示操作后，第i個(gè)字符到第j個(gè)字符按照最優(yōu)方案添加括號后的串。
輸出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) //合并字符串的函數(shù)
{
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里的數(shù)據(jù)都通不過。而且我char *after[][]是三維數(shù)組，太不方便了，代碼看起來很亂,很不爽。
想起學(xué)C語言時(shí)候，判斷括號匹配時(shí)用的是遞歸。那能不能在查找匹配時(shí)也用遞歸呢? 于是有了思路二。
思路二：
int opt[i,j]表示第i個(gè)字符到第j個(gè)字符需要添加的最少字符數(shù)，狀態(tài)轉(zhuǎn)移方程： 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]所需要插入的最小字符數(shù)
void search(int st,int end)
{
if(st>end) return;
else if(st==end){ //如果剩下最后一個(gè)字符，為之配對
if(str[st]=='('||str[st]==')')
printf("()");
else printf("[]");
}
else{
if(tag[st][end]==-1){ //如果str[st]和str[end]配對（tag==-1），打印str[st]和str[end],繼續(xù)搜索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分開的兩個(gè)子問題
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個(gè)字母到間隔len-1個(gè)字母分別計(jì)算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]可以配對，問題轉(zhuǎn)化為求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;
}