Блог пользователя red_coder

Автор red_coder, 12 лет назад, По-английски

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()); }
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Question is how to do that...

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone pls help.....

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

finally got accepted :)