1
#include<iostream>
2
using namespace std;
3
#define MAX 5000
4
5
char str[MAX+2];
6
char re_str[MAX+2];
7
//int res[MAX+1][MAX+1]; //MLE
8
int res[2][MAX+1];
9
int n;
10
11
void dp()
12

{
13
int i,j;
14
for(j=0;j<=n;j++)
15
res[0][j]=j;
16
res[1][0]=1;
17
for(i=1;i<=n;i++)
18
{
19
res[i%2][0]=i;
20
for(j=1;j<=n;j++)
21
{
22
if(str[i]==re_str[j])
23
res[i%2][j]=res[(i-1)%2][j-1];
24
else
{
25
res[i%2][j]=min(res[(i-1)%2][j],res[i%2][j-1])+1;
26
}
27
}
28
}
29
}
30
int main()
31

{
32
int i;
33
scanf("%d",&n);
34
for(i=1;i<=n;i++)
35
{
36
scanf(" %c",&str[i]);
37
re_str[n-i+1]=str[i];
38
}
39
dp();
40
printf("%d\n",res[n%2][n]>>1);
41
return 0;
42
}
//
#include<iostream>2
using namespace std;3
#define MAX 50004

5
char str[MAX+2];6
char re_str[MAX+2];7
//int res[MAX+1][MAX+1]; //MLE8
int res[2][MAX+1];9
int n;10

11
void dp()12


{13
int i,j;14
for(j=0;j<=n;j++)15
res[0][j]=j;16
res[1][0]=1;17
for(i=1;i<=n;i++)18

{19
res[i%2][0]=i;20
for(j=1;j<=n;j++)21

{22
if(str[i]==re_str[j])23
res[i%2][j]=res[(i-1)%2][j-1];24

else
{25
res[i%2][j]=min(res[(i-1)%2][j],res[i%2][j-1])+1;26
}27
}28
}29
}30
int main()31


{32
int i;33
scanf("%d",&n);34
for(i=1;i<=n;i++)35

{36
scanf(" %c",&str[i]);37
re_str[n-i+1]=str[i];38
}39
dp();40
printf("%d\n",res[n%2][n]>>1);41
return 0;42
}

