Please tell me - How to derive the recurrence equation of the cost function for editing a given string as a solution by dp?
1 Like
I am not sure, but is this what you’re looking for?
It gave a good definition for recursive nature (I copy-pasted the img below)
BTW, another Q for you to think now. What would you do if I state that that costs are not same, i.e. cost of removing a character, replacing a character and adding a character aren’t same?
Also, what if more possibilities were added? (I think one of the DEC Long Q had tweaked this by “additionally, you can swap two characters”…)
1 Like
I am not sure but i think it can be
for each i=1…m
for each j=1…n
D(i,j)=min{D(i-1,j)+1
D(i,j-1)+1
D(i-1,j-1) + 2; {if x[i] not equal y[j]
0; if x[i] = y[j]
1 Like