Dynamic Programming - Edit Distance

문제는
given two string x y, what's the cheapest possible sequence of char edits to turn x -> y
insert, delete, replace가 가능하고 각 edit의 cost는 정해져 있다.

예를 들어,
HIEROGLYPHOLOGY,  MICHAELANGELO 이 두 단어의 edit distance는 얼마일까?

우선 subproblem을 define해야 한다.
일단 스트링이 나오니까 prefix, suffix, substring중의 하나라고 볼 수 있다.
두개의 스트링이 나오니까 이들 2개의 조합일것이라 추측이 가능하다.

prefix 혹은 suffix기반의 recurrence식을 만들 수 있다.
prefix기반은 이렇게 된다.

유사하게 suffix 기반의 recurrence 식도 만들 수 있다. 이것은 여기서 설명하진 않고 github 소스에 구현되 있으므로 이를 참고하면 되겠다.


reference :
http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/