dp,LCS的应用
//求出输入的字符串和他的回文串的LCS的长度l，用此字符串的长度n-l，即得结果
//还有存储的问题，如果用f[maxn][maxn]存储的话会超内存，可通过滚动数组优化
//因为求当前f[i][j]时可能会用到f[i-1][j-1],f[i-1][j],f[i][j-1],观察发现i,j
//只用到当前的i,i-1，二者可用奇偶性区分，只需用一个f[i%2][j]就可表示，为什么
//不能用f[i][j%2]表示，可通过判定求当前的f[i][j%2]时，f[i-1][j%2]并不是f[i-1][j]
//所以这样做是错误的，但前者却可以通过类似的方法判是正确的，所以只需f[2][maxn]的空间
//就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=5002;
const int inf=1<<30;
char s[maxn],p[maxn];
int f[2][maxn];
int main()
{
int n;
while(cin>>n)
{
getchar();
int i,j;
char c;
for(i=1;i<=n;i++)
{
scanf("%c",&c);
s[i]=c;p[n+1-i]=c;
}
s[n+1]='\0';p[n+1]='\0';
memset(f,0,sizeof(f));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
f[i%2][j]=inf;
if(s[i]==p[j])
f[i%2][j]=f[(i-1)%2][j-1]+1;
else
f[i%2][j]=f[(i-1)%2][j]>f[i%2][j-1]?f[(i-1)%2][j]:f[i%2][j-1];
}
}
cout<<n-f[n%2][n]<<endl;
}
return 0;
}