Derive the recurrence equation of the cost function for editihing a given string

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)

alt text

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