[POJ] 1159 - Palindrome

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
string A,B;
short dp[5005][5005]={0};
char s[5005];
int main(){
    int n,i,j,ans=999999999;
    scanf("%d%s",&n,s);
    A=string(s);
    for(i=n-1;i>=0;i--)
        B+=A[i];
    A=' '+A;
    B=' '+B;
    for(i=1;i<A.size();i++)
        for(j=1;j<B.size();j++){
            if(A[i]==B[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    for(i=1;i<A.size();i++){
        if(n-1-dp[i-1][n-i]*2<ans)
            ans=n-1-dp[i-1][n-i]*2;
        if(n-dp[i][n-i]*2<ans)
            ans=n-dp[i][n-i]*2;
    }
    printf("%d\n",ans);
}