×

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

 1 Please tell me - How to derive the recurrence equation of the cost function for editing a given string as a solution by dp? asked 24 Mar '17, 22:20 2★rashedcs 497●5●16●54 accept rate: 4%

 1 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"...) answered 25 Mar '17, 01:10 15.2k●1●18●59 accept rate: 18%
 1 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] answered 18 Apr '17, 20:38 11●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,086
×152

question asked: 24 Mar '17, 22:20

question was seen: 455 times

last updated: 18 Apr '17, 20:38