1.定義
假設(shè)只有三種編輯方式：插入城须，刪除，替換凹蜈。每種編輯方式對應(yīng)一次操作限寞。按規(guī)定的編輯方式，將原始字符串變換到目標(biāo)字符串所需的最少操作次數(shù)仰坦，被稱為最小編輯距離履植。
Levenshtein距離中定義替換對應(yīng)兩次操作。
2.推導(dǎo)
設(shè)源字符串為A悄晃，長度m玫霎，目標(biāo)字符串為B，長度n妈橄。
是否存在簡單情況
很明顯庶近，兩字符串長度較短時情況會比較簡單。
如眷蚓，m=0時鼻种，插入n次；n=0時沙热，刪除n次叉钥；m=n=1且A和B不同時罢缸，替換1次。簡單情況到復(fù)雜情況的變量是什么
是兩個字符串的長度投队。因此我們設(shè)最小編輯距離為枫疆。
是否存在簡單情況到復(fù)雜情況的遞推關(guān)系
由1有
從向前回溯，有三條路徑敷鸦，對應(yīng)三種編輯方式息楔，
這里，
扒披，
钞螟，
。
- 每一步取最短路徑谎碍，最后一定是最短路徑嗎鳞滨？對于每次都?xì)w結(jié)于一點的樹形結(jié)構(gòu)，這是必然的蟆淀。
