#include <stdio.h>
short int l[5001][5001];
char s[5001];
int love(int i, int j)//自上而下的动态规划(备忘录法)
{
	if(l[i][j]!=5555)
		return l[i][j];
	if(j<=i)
	{
		l[i][j]=0;
		return 0;
	}
	if(s[i]==s[j])
	{
		l[i][j]=love(i+1,j-1);	
		return l[i][j];
	}
	else
	{
		l[i][j]=love(i+1,j);
		if(love(i,j-1)<l[i][j])
			l[i][j]=l[i][j-1];
		l[i][j]++;
		return l[i][j];
	}
}
int main()
{
	int n,i,j;
	scanf("%d%s",&n,s);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			l[i][j]=5555;
	printf("%d",love(0,n-1));
}
/*刻画最优子结构的解为：设l[i,j]为s[i..j]之间最少需插入的字符个数。
		{
		 0							i=j;
l[i,j]=	 l[i+1,j-1]					s[i]=s[j]&&j>=i;
		 min(s[i+1,j],s[i,j-1])+1	s[i]!=s[j]&&j>=i;
        }*/

• 看 F.A.Qs (773) sEMpRMAjIA 2006-08-20 16:43:05