用a[2][n]的存储空间;
http://acm.pku.edu.cn/JudgeOnline/problem?id=1159

#include <stdio.h>
int main()
{
    int a[2][5002]={0};
    char p[5002];
    char ch[5002];
    int i,j,n,t;
    int current;
    int before;
    scanf("%d%s",&n,p+1);

        current=1;
        before = 0;
        for(i=1;i<=n;i++)
           ch[i]=p[n-i+1];
           ch[i]='\0';
     //   printf("%s %s\n",p+1,ch+1);
        for(i=1;i<=n;i++)
        {    for(j=1;j<=n;j++)
                if(ch[i]==p[j])
                   a[current][j]=a[before][j-1]+1;
                else
                    if(a[current][j-1]>=a[before][j])a[current][j]=a[current][j-1];
                    else a[current][j]=a[before][j];
              t=current;
              current=before;
              before=t;
        }
        printf("%d\n",n-a[t][n]);
    return 0;
}

其他题目：
http://acm.pku.edu.cn/JudgeOnline/problem?id=2533