You are not logged in. Please login at www.codechef.com to post your questions!

×

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?

asked 24 Mar '17, 22:20

rashedcs's gravatar image

2★rashedcs
49731044
accept rate: 4%


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"...)

link

answered 25 Mar '17, 01:10

vijju123's gravatar image

5★vijju123 ♦
13.1k1730
accept rate: 19%

edited 25 Mar '17, 01:16

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]

link

answered 18 Apr '17, 20:38

mahedi_hasan's gravatar image

1★mahedi_hasan
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×1,671
×129

question asked: 24 Mar '17, 22:20

question was seen: 419 times

last updated: 18 Apr '17, 20:38