checkMate09's blog

Dynamic Programming Classical String Alignment aka Edit Distance

By checkMate09, history, 8 years ago, In English

Hello Codeforces, i have tried to understand Edit Distance Dynamic Programming classical problem and i tried few tutorials through the internet and i couldn't understand the concept. can any one clarify it to me in very simple way ?

  • Vote: I like it
  • -7
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

State with index x, y on table: minimum number of edits required to convert prefix of first string with legth x into prefix of second string with legth y;

Transitions: Possibles operations;

Or try it: http://bfy.tw/6TFq

→ Reply