学步园

//196K   
797MS
#include <stdio.h>
#include <string.h>
#define M 5002
short int c[2][M];
char s1[M],s2[M];
int Max (int a,int b)
{
    return a
> b ? a : b;
}
int DP (int n)
{
    int
i,j,k;
    for (i = 0;
i <= n; i ++)
       
c[0][i] = 0;
    k = 1;
    for (i = 1;
i <= n; i ++)
    {
       
for (j = 1; j <= n; j ++)
           
if (s1[i] == s2[j])
               
c[k][j] = c[k-1][j-1] + 1;
           
else
               
c[k][j] = Max (c[k-1][j],c[k][j-1]);
       
memcpy (c[0],c[1],sizeof(c[0]));
    }
    return
c[1][n];
}
int main ()
{
    int
n,i,k;
    while
(~scanf ("%d",&n))
    {
       
getchar ();
       
gets (s1+1);
       
k = 1;
       
for (i = n; i > 0; i --)
           
s2[k++] = s1[i];
       
int max = DP (n);
       
printf ("%d\n",n-max);
    }
}