Mukit09's blog

By Mukit09, 5 years ago, In English,

I am new in DP... Now trying to learn edit distance algorithm recursively... But I can't print the path... How can I do this ???

I have been trying since last two days but can't get it... :(

Would anyone please check the code given in the link below and tell me where should I edit to print the path correctly ???

code link

  • Vote: I like it  
  • -1
  • Vote: I do not like it  

5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In order to print the path you need to backtrack.

For example, suppose you are storing results of your subproblems in DP[i][j], what can done is to also store the decision that you made at that step in a separate matrix call it B[i][j].

In this case, DP[i][j]=min{DP[i-1][j]+1,DP[i][j-1]+1,DP[i-1][j-1] if s[i]=t[j], else DP[i-1][j-1]+1}

you can store in BP[i][j] the choice which gave you the min. For example if DP[i][j-1]+1, gave you the min. store (i,j-1) in BP[i][j] as a pair. So you know that at (i,j) you had chosen to delete a character and that before taking that decision you were at BP[i][j-1].

Now in order to print the path start with BP[m][n] and then backtrack using information you had stored in table BP[i][j].

  • »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    thanks... got it... :)

    • »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      we can print path instead of new array by dp array ...

      we start last position of dp array untill position is zero...

      1.if array1[i-1]==array2[j-1] we do nothing ...

      2.if dp[i][j]==dp[i-1][j]+1 (trick: s1.leangth>s2.leangth) then we delete the (i-1)th character from the first array

      3.if dp[i][j]==dp[i][j-1]+1 (trick: s1.leangth<s2.leangth) then we insert the (j-1)th
      character from the second array into the (i+1)th position in the first array ...

      4.if dp[i][j]==dp[i-1][j-1]+1 then we change the (j-1)th character in the first array by (j-1)th character in the second array...

      code(UVA 164) link :-