前幾天在網(wǎng)上看到一份鵝場(chǎng)的面試題，算法部分大半是動(dòng)態(tài)規(guī)劃，最后一題就是寫一個(gè)計(jì)算編輯距離的函數(shù)，今天就專門寫一篇文章來探討一下這個(gè)經(jīng)典問題。

我個(gè)人很喜歡編輯距離這個(gè)問題，因?yàn)樗雌饋硎掷щy，解法卻出奇得簡(jiǎn)單漂亮，而且它是少有的比較實(shí)用的算法（是的，我承認(rèn)很多算法問題都不太實(shí)用）。下面先來看下題目：

為什么說這個(gè)問題難呢，因?yàn)轱@而易見，它就是難，讓人手足無措，望而生畏。

為什么說它實(shí)用呢，因?yàn)榍皫滋煳揖驮谌粘Ｉ钪杏玫搅诉@個(gè)算法。之前有一篇公眾號(hào)文章由于疏忽，寫錯(cuò)位了一段內(nèi)容，我決定修改這部分內(nèi)容讓邏輯通順。但是公眾號(hào)文章最多只能修改 20 個(gè)字，且只支持增、刪、替換操作（跟編輯距離問題一模一樣），于是我就用算法求出了一個(gè)最優(yōu)方案，只用了 16 步就完成了修改。

再比如高大上一點(diǎn)的應(yīng)用，DNA 序列是由 A,G,C,T 組成的序列，可以類比成字符串。編輯距離可以衡量?jī)蓚€(gè) DNA 序列的相似度，編輯距離越小，說明這兩段 DNA 越相似，說不定這倆 DNA 的主人是遠(yuǎn)古近親啥的。

下面言歸正傳，詳細(xì)講解一下編輯距離該怎么算，相信本文會(huì)讓你有收獲。

一、思路

編輯距離問題就是給我們兩個(gè)字符串s1和s2，只能用三種操作，讓我們把s1變成s2，求最少的操作數(shù)。需要明確的是，不管是把s1變成s2還是反過來，結(jié)果都是一樣的，所以后文就以s1變成s2舉例。

前文 最長(zhǎng)公共子序列 說過，解決兩個(gè)字符串的動(dòng)態(tài)規(guī)劃問題，一般都是用兩個(gè)指針i,j分別指向兩個(gè)字符串的最后，然后一步步往前走，縮小問題的規(guī)模。

設(shè)兩個(gè)字符串分別為 'rad' 和 'apple'，為了把s1變成s2，算法會(huì)這樣進(jìn)行：

根據(jù)上面的 GIF，可以發(fā)現(xiàn)操作不只有三個(gè)，其實(shí)還有第四個(gè)操作，就是什么都不要做（skip）。比如這個(gè)情況：

因?yàn)檫@兩個(gè)字符本來就相同，為了使編輯距離最小，顯然不應(yīng)該對(duì)它們有任何操作，直接往前移動(dòng)i,j即可。

還有一個(gè)很容易處理的情況，就是j走完s2時(shí)，如果i還沒走完s1，那么只能用刪除操作把s1縮短為s2。比如這個(gè)情況：

類似的，如果i走完s1時(shí)j還沒走完了s2，那就只能用插入操作把s2剩下的字符全部插入s1。等會(huì)會(huì)看到，這兩種情況就是算法的 base case。

下面詳解一下如何將這個(gè)思路轉(zhuǎn)化成代碼，坐穩(wěn)，準(zhǔn)備發(fā)車了。

二、代碼詳解

先梳理一下之前的思路：

base case 是i走完s1或j走完s2，可以直接返回另一個(gè)字符串剩下的長(zhǎng)度。

對(duì)于每對(duì)兒字符s1[i]和s2[j]，可以有四種操作：

有這個(gè)框架，問題就已經(jīng)解決了。讀者也許會(huì)問，這個(gè)「三選一」到底該怎么選擇呢？很簡(jiǎn)單，全試一遍，哪個(gè)操作最后得到的編輯距離最小，就選誰。這里需要遞歸技巧，理解需要點(diǎn)技巧，先看下代碼：

下面來詳細(xì)解釋一下這段遞歸代碼，base case 應(yīng)該不用解釋了，主要解釋一下遞歸部分。

都說遞歸代碼的可解釋性很好，這是有道理的，只要理解函數(shù)的定義，就能很清楚地理解算法的邏輯。我們這里 dp(i, j) 函數(shù)的定義是這樣的：

def dp(i, j) -> int
# 返回 s1[0..i] 和 s2[0..j] 的最小編輯距離

記住這個(gè)定義之后，先來看這段代碼：

如果s1[i]！=s2[j]，就要對(duì)三個(gè)操作遞歸了，稍微需要點(diǎn)思考：

dp(i, j - 1) + 1,    # 插入
# 解釋：
# 我直接在 s1[i] 插入一個(gè)和 s2[j] 一樣的字符
# 那么 s2[j] 就被匹配了，前移 j，繼續(xù)跟 i 對(duì)比
# 別忘了操作數(shù)加一

dp(i - 1, j - 1) + 1 # 替換
# 解釋：
# 我直接把 s1[i] 替換成 s2[j]，這樣它倆就匹配了
# 同時(shí)前移 i，j 繼續(xù)對(duì)比
# 操作數(shù)加一

現(xiàn)在，你應(yīng)該完全理解這段短小精悍的代碼了。還有點(diǎn)小問題就是，這個(gè)解法是暴力解法，存在重疊子問題，需要用動(dòng)態(tài)規(guī)劃技巧來優(yōu)化。

怎么能一眼看出存在重疊子問題呢？前文 動(dòng)態(tài)規(guī)劃之正則表達(dá)式 有提過，這里再簡(jiǎn)單提一下，需要抽象出本文算法的遞歸框架：

對(duì)于子問題dp(i-1,j-1)，如何通過原問題dp(i,j)得到呢？有不止一條路徑，比如dp(i,j)->#1和dp(i,j)->#2->#3。一旦發(fā)現(xiàn)一條重復(fù)路徑，就說明存在巨量重復(fù)路徑，也就是重疊子問題。

三、動(dòng)態(tài)規(guī)劃優(yōu)化

對(duì)于重疊子問題呢，前文 動(dòng)態(tài)規(guī)劃詳解 介紹過，優(yōu)化方法無非是備忘錄或者 DP table。

備忘錄很好加，原來的代碼稍加修改即可：

def minDistance(s1, s2) -> int:

    memo = dict() # 備忘錄
    def dp(i, j):
        if (i, j) in memo: 
            return memo[(i, j)]
        ...

        if s1[i] == s2[j]:
            memo[(i, j)] = ...  
        else:
            memo[(i, j)] = ...
        return memo[(i, j)]

    return dp(len(s1) - 1, len(s2) - 1)

主要說下 DP table 的解法：

首先明確 dp 數(shù)組的含義，dp 數(shù)組是一個(gè)二維數(shù)組，長(zhǎng)這樣：

dp[i][j]的含義和之前的 dp 函數(shù)類似：

有了之前遞歸解法的鋪墊，應(yīng)該很容易理解。dp 函數(shù)的 base case 是i,j等于 -1，而數(shù)組索引至少是 0，所以 dp 數(shù)組會(huì)偏移一位，dp[..][0]和dp[0][..]對(duì)應(yīng) base case。。

既然 dp 數(shù)組和遞歸 dp 函數(shù)含義一樣，也就可以直接套用之前的思路寫代碼，唯一不同的是，DP table 是自底向上求解，遞歸解法是自頂向下求解：

三、擴(kuò)展延伸

一般來說，處理兩個(gè)字符串的動(dòng)態(tài)規(guī)劃問題，都是按本文的思路處理，建立 DP table。為什么呢，因?yàn)橐子谡页鰻顟B(tài)轉(zhuǎn)移的關(guān)系，比如編輯距離的 DP table：

還有一個(gè)細(xì)節(jié)，既然每個(gè)dp[i][j]只和它附近的三個(gè)狀態(tài)有關(guān)，空間復(fù)雜度是可以壓縮成 O(min(M,N)) 的（M，N 是兩個(gè)字符串的長(zhǎng)度）。不難，但是可解釋性大大降低，讀者可以自己嘗試優(yōu)化一下。

你可能還會(huì)問，這里只求出了最小的編輯距離，那具體的操作是什么？之前舉的修改公眾號(hào)文章的例子，只有一個(gè)最小編輯距離肯定不夠，還得知道具體怎么修改才行。

這個(gè)其實(shí)很簡(jiǎn)單，代碼稍加修改，給 dp 數(shù)組增加額外的信息即可：

// int[][] dp;
Node[][] dp;

class Node {
    int val;
    int choice;
    // 0 代表啥都不做
    // 1 代表插入
    // 2 代表刪除
    // 3 代表替換
}

val屬性就是之前的 dp 數(shù)組的數(shù)值，choice屬性代表操作。在做最優(yōu)選擇時(shí)，順便把操作記錄下來，然后就從結(jié)果反推具體操作。

我們的最終結(jié)果不是dp[m][n]嗎，這里的val存著最小編輯距離，choice存著最后一個(gè)操作，比如說是插入操作，那么就可以左移一格：

重復(fù)此過程，可以一步步回到起點(diǎn)dp[0][0]，形成一條路徑，按這條路徑上的操作編輯對(duì)應(yīng)索引的字符，就是最佳方案：

這就是編輯距離算法的全部?jī)?nèi)容，希望本文對(duì)你有幫助。