經(jīng)典的動(dòng)態(tài)規(guī)劃題。
d[i][j]表示把從1..i和j..n變成回文詞最少需要的字符個(gè)數(shù)。
則：d[i][j]=min(d[i][j],d[i-1][j+1]) s[i]==s[j]；
d[i][j]=min(d[i][j],d[i-1][j]+1)；
d[i][j]=min(d[i][j],d[i][j+1]+1)；
以下是我的程序：
#include<stdio.h>
#define maxn 5005
#define maxint 20000
#define min(a,b) (a<b?a:b)
char ch,s[maxn]=
{0};
short i,j,n,ans,d[maxn][maxn];
int main()
{
freopen("palin.in","r",stdin);
freopen("palin.out","w",stdout);
scanf("%ld\n",&n);
for(i=1;i<=n;i++)
scanf("%c",&s[i]);
for(i=0;i<=n+2;i++)
for(j=0;j<=n+2;j++)
d[i][j]=maxint;
// Init
d[0][n+1]=0;
d[0][n]=1;
d[1][n+1]=1;
// 邊界
for(i=1;i<=n+1;i++)
for(j=n+1;j>=i;j--)
{
if(s[i]==s[j])
d[i][j]=min(d[i][j],d[i-1][j+1]);
d[i][j]=min(d[i][j],d[i-1][j]+1);
d[i][j]=min(d[i][j],d[i][j+1]+1);
}
// DP
ans=maxint;
for(i=1;i<=n;i++)
{
ans=min(ans,d[i][i]);
ans=min(ans,d[i][i+1]);
}
// Find Answer
printf("%d\n",ans);
return 0;
}