hey guys here is a simple DP Problem, to solve it i found the LCS of original and reversed string and then substracted this length from the length of given string. I am getting TLE. I used a bottom-up approach.My code is given below.Can anyone help me out??
char A[5005];
int L[5005][5005];
int n;
int ch() //this function calculates the LCS of original string and reversed string
{
f(i,0,n)
{
f(j,0,n)
{
if(A[i]==A[n-1-j])
{
L[i][j]=1;
if(i!=0 && j!=0)
L[i][j]+=L[i-1][j-1];
}
else
{
int x=0,y=0;
if(i>0) x=L[i-1][j];
if(j>0) y=L[i][j-1];
L[i][j]=max(x,y);
}
}
}
return L[n-1][n-1];
}
int main()
{
si(n);
scanf("%s",A);
//puts(B);
printf("%d\n",n-ch());
}
I think it is a Levenshtein distance problem..[link]
You should try to reduce the size of L. It does help a lot.
Question is how to do that...
Observe that L(i,j) is only dependent on L(i-1, j') and L(i,j') ==> you can reuse the memory of L in previous rows.
Someone pls help.....
finally got accepted :)