關(guān)于最小編輯距離的動態(tài)規(guī)劃求解，網(wǎng)上有很多解釋，但是又很長，看著費(fèi)勁，理解也費(fèi)勁，這里進(jìn)行一下提煉。

最小編輯距離可以用遞歸來解，但是動態(tài)規(guī)劃是更簡潔的，效率達(dá)到O(mn)。構(gòu)建動態(tài)規(guī)劃思想的是用空間換時間，將計算過的就不再計算（對遞歸方法的優(yōu)化），直接調(diào)取記錄值。所以關(guān)鍵再與怎么用到已經(jīng)有記錄的值，建立前后聯(lián)系。

一般二維記錄矩陣都是考慮[i，j]位置和[i-1，j-1]，[i，j-1]，[i-1，j]位置處數(shù)值的關(guān)系（比如最小編輯距離【[i-1，j-1]，[i，j-1]，[i-1，j]】，最長公共子序列【[i，j-1]，[i-1，j]位置處】，最小行走距離【[i-1，j-1]，[i，j-1]，[i-1，j]】），或者是有別的聯(lián)系（限制）的位置處（比如背包問題【W(wǎng)-w[i]位】）。

一維矩陣的話一般是考慮前1位或者前2位（比如跳臺階【[i-1]，[1-2]位】），或者其他限制和聯(lián)系（比如最長遞增子序列【前j位】）。最小Floyd路徑則更為復(fù)雜，它的記錄矩陣式二維矩陣，但是與某一[i，j]位置相關(guān)的有很多，他的核心是減少中間節(jié)點(diǎn)，所以可能i，j中間的都和它有關(guān)。

最小編輯距離（也成為Levenshtein）是指：把字符串1編輯成字符串2所需的最小步驟?？捎玫木庉嫹椒ㄓ胁迦耄瑒h除，替換。這類題目又分為又權(quán)重和無權(quán)重。

建立查詢數(shù)組arr，數(shù)組的行數(shù)為a的長度加1，列數(shù)為b的長度加1，也就是再原來的基礎(chǔ)上再考慮了空對空的情況。

先考慮將arr的第一行設(shè)置為空字符編輯成b的距離，也就是依次插入

arr[0][j]=j

再考慮將arr的第一列設(shè)置為a編輯成空字符串的距離，也就是依次刪除

arr[i][0] = i

從字符串a(chǎn)到字符串b有三種編輯方式那么我們分別考慮三種方式，

刪除：arr[i][j] = arr[i-1][j]+cost_delete，就是先刪除a的第i位，再將前i-1位編輯成b的前j位

插入：arr[i][j] = arr[i][j-1]+cost_insert，就是先將a的前i位編輯成b的前j-1位，然后再插入一位a[i]

替換：arr[i][j] arr[i-1][j-1] + cost_inplace，就是先將a的前i-1位編輯成b的前i-1位，然后將a的第i位替換成b的第j位

參考：來源