用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