SPOJ IOPALIN

general
, , ,
1

in http://www.spoj.com/problems/IOIPALIN/ , I tried to solve with DP,LCS but getting TLE everytime.
my solution

2

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n; //length of the string
scanf("%d",&n);
char str[5009];
scanf("%s",str);
char str2[5009];

int dp[5009][5009]={0};
int i;
for(i=0;i<=n-1;i++)
    str2[i]=str[n-1-i];
for(i=1;i<=n;i++)
{
    int j;
    for(j=1;j<=n;j++)
    {
        if(str[i-1]==str2[j-1])
            dp[i][j]=dp[i-1][j-1]+1;
        else
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    }
}
cout<<n-dp[n][n]<<"\n";//dp[n][m]=length of longest common subsequence
return 0;//length of original string-length of lcs is the answer

}