#include <iostream>
using namespace std;
const short maxn=5001;
char s[maxn];
int i,j,k,n;
short f[maxn][maxn];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	memset(f,0,sizeof(f));
	for(i=1;i<n;i++)
	    for(j=1;j<=n-i;j++)
	    {
	    	k=j+i;
	    	if(s[j]==s[k]) f[j][k]=f[j+1][k-1];
	    	else f[j][k]=((f[j+1][k]<f[j][k-1])?f[j+1][k]:f[j][k-1])+1;
		}
	printf("%d\n",f[1][n]);
	return 0;
}

• Re:按照普通的DP方法AC了，此题很多细节需要注意，程序仅供参考。 (31) Sasuke_SCUT 2009-03-04 10:51:43