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 ???

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].

thanks... got 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 :- https://ideone.com/h2k7z3