1873454_wa.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>

char str[5001];
short d[5001][5001]={0};

int main()
{
 int n, i, j;
 
 scanf("%d%s",&n,str);
 for(i = 0; i <= n;d[i][0]=d[0][i]=0,i++);
 
 for(i = 1; i <= n; i++)
  {
   for(j = n; j > 0; j--)
   if(i<j) continue;
    if(str[i-1]==str[j-1])
     d[i][n-j+1]=d[i-1][n-j]+1;
    else if(d[i][n-j]>d[i-1][n-j+1])
             d[i][n-j+1]=d[i][n-j];
         else d[i][n-j+1]=d[i-1][n-j+1];
  }
         printf("%d\n",n-d[n][n]);
  return 1;
}