引用大牛lnmm的思路

设ch[1]..ch[n]表示字符串1至n位，i为左游标，j为右游标 ，则i从n递减，j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n]. 则
if(ch[i]==ch[j])                                    //如果两个游标所指字符相同，向中间缩小范围
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 +  （min[i+1][j]和min[i][j-1]中的较小值）;     //如果不同，典型的状态转换方程

画个图

i\j  1    2    3    4    5
1    0    *    *    *    *
2    0    0    *    *    *
3         0    0    *    *
4              0    0    *
5                   0    0

求右上的三角形即可, 三个方向, 左, 下, 左下, 和算法导论里353页的图思路差不多, 意思不一样而已.
一个自以为比较有意思的空间优化是, 把头顺时针转45度看那个三角形.. 不讲了麻烦, 上代码..

404K 344MS G++

#include <stdio.h>

int main()
{
    int n;
    char a[5010];
    scanf("%d",&n);
    while(getchar()!='\n');
    scanf("%s",a);

    int c[10010];
    for(int i=2;i<=2*n;i++) {
        c[i]=0;
    }

    for(int x=1;x<=n-1;x++)
        for(int i=1;i<=n-x;i++) {
            int j=i+x;
            char ai=a[i-1],aj=a[j-1];
            if(ai==aj)
                continue;
            c[i+j]=c[i+j-1]<c[i+j+1]?c[i+j-1]:c[i+j+1];
            c[i+j]++;
        }
    printf("%d\n",c[1+n]);

    return 0;
}