DjvuLee

//@pku DY问题
//最重要的是要找到重叠子问题，本题用LCS的方法是错误的
//本题最大的问题是flag数组太大，用int会MLE，改用short可以勉强通过
//感觉每次用备忘录的方法时内存的开销都是一个很大的问题
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

#define N 5010
short flag[N][N];
string s;
int dp(int low,int high);
int main()
{
    int n;
    while(cin>>n){
        int cn=0;
        cin>>s;
        memset(flag,-1,sizeof(flag));

        cn=dp(0,n-1);
        cout<<cn<<endl;
    }//end while
    return 0;
}


int dp(int low,int high)
{
    if(low>=high)
        return 0;
    else
    {
        if(flag[low][high]!=-1)
            return flag[low][high];

        else
        {
            if(s[low]==s[high])
                return flag[low+1][high-1]=dp(low+1,high-1);
            else
            {
                flag[low+1][high]=dp(low+1, high);
                flag[low][high-1]=dp(low, high-1);
                return flag[low][high]=1+min(flag[low+1][high],flag[low][high-1]);
            }
        }
    }
}