red_coder's blog

By red_coder, 12 years ago, In English

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()); }
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
Rev. 3   Vote: I like it -6 Vote: I do not like it

I think it is a Levenshtein distance problem..[link]

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should try to reduce the size of L. It does help a lot.

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Question is how to do that...

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone pls help.....

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

finally got accepted :)