這篇文章是我在做一道有關(guān)字符串的算法題時(shí)候想把這個(gè)過(guò)程記錄下來(lái)，加深一下印象。

先上原題：

編輯距離，又稱(chēng)Levenshtein距離（也叫做Edit Distance），是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。
例如將kitten一字轉(zhuǎn)成sitting：
sitten （k->s）
sittin （e->i）
sitting （->g）
所以kitten和sitting的編輯距離是3。俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出這個(gè)概念。
給出兩個(gè)字符串a(chǎn),b，求a和b的編輯距離。
Input
第1行：字符串a(chǎn)(a的長(zhǎng)度 <= 1000)。
第2行：字符串b(b的長(zhǎng)度 <= 1000)。
Output
輸出a和b的編輯距離
Input示例
kitten
sitting
Output示例
3

這道題其實(shí)很經(jīng)典，是利用了上面那個(gè)科學(xué)家發(fā)現(xiàn)的經(jīng)典算法。第一次遇見(jiàn)，主要是想訓(xùn)練一下字符串相關(guān)的題目，然后這道題是涉及使用動(dòng)態(tài)規(guī)劃的一道經(jīng)典題目

這道題的思路比較簡(jiǎn)單，但是對(duì)于初學(xué)動(dòng)態(tài)規(guī)劃和算法的我來(lái)說(shuō)，確實(shí)不好想。

思路：
先將兩個(gè)字符串都在開(kāi)頭加上一個(gè)空格，為了后面動(dòng)態(tài)規(guī)劃處理時(shí)，在第一個(gè)字符也能有前面的結(jié)果作為基礎(chǔ)。比如要是不加空格，那么開(kāi)頭的第一個(gè)字符就沒(méi)法向前尋找結(jié)果。
規(guī)定：
dp[i][j]為處理字符串a(chǎn)前i個(gè)字符編輯成字符串b前j個(gè)字符所需要的距離。也就是操作次數(shù)
如果當(dāng)s1[i]==s2[j] 那么dp[i][j]=dp[i-1][j-1]
因?yàn)槟阆?，第i個(gè)字符和j字符相同，那么此時(shí)是不需要進(jìn)行任何操作的,也就和dp[i-1][j-1]相等了。
如果當(dāng)前i和j位置不同 那么dp[i][j]有三個(gè)狀態(tài)轉(zhuǎn)移方式：
dp[i-1][j]+1 在a串的i位置刪除a[i] (或者在b串的i位置加上a[i])
dp[i][j-1]+1 在b串的j位置刪除b[j] (或者在a串的j位置加上b[j])
dp[i-1][j-1]+1 在a串的i位置改a[i]變成b[j]或者在b串的j位置改b[j]為a[i]

當(dāng)時(shí)的我看到這些東西的時(shí)候也是很懵逼的，第一次對(duì)我這種菜鳥(niǎo)來(lái)說(shuō)確實(shí)不好理解。

下面我上圖來(lái)說(shuō)明一下情況，幫助理解這些狀態(tài)變化的理由

1. 第一種情況 s1[i]==s2[j]

i和j位置上的字符相同

因?yàn)榇藭r(shí)這兩個(gè)位置相同 那么dp[i][j]的意思 是字符串a(chǎn)從0-i和字符串b從0到j(luò)所需要的編輯操作次數(shù)，那么就會(huì)等于dp[i-1][j-1]因?yàn)閕和j相等無(wú)需操作。

2. 第二種情況 s1[i]!=s2[j]

i和j位置上的字符不相同

狀態(tài)轉(zhuǎn)移1： dp[i-1][j]+1

看圖理解

首先我們看左邊部分dp[i-1][j]在圖中代表的就是橙色部分，也就是編輯成橙色部分需要的操作次數(shù)，那么我們現(xiàn)在在這個(gè)圖的基礎(chǔ)上如何變成dp[i][j]呢，我可以在b串的橙色部分基礎(chǔ)上，在i位置插入a串的i位置的字符。就變成 了右圖的形式。此時(shí)也就形成了dp[i][j]（至于那么刪除a串i位置是怎么解釋?zhuān)乙粫r(shí)間想不明白。還請(qǐng)讀者幫忙解惑評(píng)論一下，我再把文章更新。非常感謝！）

狀態(tài)轉(zhuǎn)移2： dp[i][j-1]+1

原理同上，就是調(diào)換一下兩個(gè)串即可。

狀態(tài)轉(zhuǎn)移3： dp[i-1][j-1]+1

看圖理解

首先我們看圖的左半部分，橙色表示dp[i-1][j-1]。那么我們?nèi)绾稳ジ淖內(nèi)p[i][j]呢，因?yàn)檫@種情況的前提條件是i位置和j位置的字符不相同。那么我們只需要替換字符即可，把i位置的字符替換成j位置的或者反過(guò)來(lái)都是一樣的。變成右邊部分。綠色的字符就是我們調(diào)整后的字符。然后就形成了dp[i][j]了。

代碼C++實(shí)現(xiàn)：

#include <iostream>
#include <string>
using namespace std;

const int N=1000;

int dp[N+1][N+1];

int min(int a,int b)
{
    return a>b?b:a;
}

/*
狀態(tài)轉(zhuǎn)移：
若a串第i個(gè)與b串第j個(gè)相等，那么dp[i][j]=dp[i-1][j-1]
否則，dp[i][j]可由3個(gè)狀態(tài)轉(zhuǎn)移而來(lái)：
①dp[i-1][j-1]+1 把a(bǔ)[i]改為b[j] 等價(jià)于把b[j]改為a[i]
②dp[i-1][j]+1 刪去a[i] 等價(jià)于在b[j]前插入a[i]
③dp[i][j-1]+1 刪去b[j]，等價(jià)于在a[i]前插入b[j] 
初始化:dp[0][i]=i  dp[i][0]=i
*/

int main()
{
    string s1;
    string s2;

    cin>>s1>>s2;

    s1=" "+s1;//前面補(bǔ)充一個(gè)空格
    s2=" "+s2;//前面補(bǔ)充一個(gè)空格

    int i,j;
    int len1,len2;
    len1=s1.size();
    len2=s2.size();//dp[i][j] 代表 s1前i個(gè)字符和s2前j個(gè)字符的編輯距離
    

    for(i=1;i<len1;i++)
    {
        dp[0][i]=i;
    }
    
    for(i=1;i<len2;i++)
    {
        dp[i][0]=i;
    }

    for(i=1;i<=len1;i++)
    {
        for(j=1;j<=len2;j++)
        {
            if(s1[i]==s2[j])
            {
                dp[i][j]=dp[i-1][j-1];
            }
            else
            {
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            }
        }
    }

    cout<<dp[len1][len2]<<endl;
    return 0;
}