給定兩個(gè)字符串word1以及word2，返回將word1轉(zhuǎn)為word2需要的最少步驟，在每一步中你可以針對(duì)字符串word1進(jìn)行以下操作：

新增一個(gè)字符

刪除一個(gè)字符

替換一個(gè)字符

假如word1是"horse"，word2是“ros”，那么你的程序需要返回3，也就是說(shuō)將word1轉(zhuǎn)為word2至少需要三個(gè)步驟：

將word1中的第一個(gè)字符h替換為字符r：horse -> rorse，此時(shí)word1變?yōu)閞orse，word1與word2前兩個(gè)字符相等

將word1中的第三個(gè)字符r刪掉：rorse -> rose，此時(shí)word1變?yōu)閞ose，word1與word2的前三個(gè)字符相等

將word1中的最后一個(gè)字符刪掉：rose -> ros，此時(shí)word1與word2相等。

想一想該怎樣用動(dòng)態(tài)規(guī)劃解決這個(gè)問(wèn)題。

選擇與子問(wèn)題

和之前的題目一樣，你首先應(yīng)該找出子問(wèn)題是什么，子問(wèn)題與原始問(wèn)題的依賴(lài)關(guān)系是什么。

找出子問(wèn)題的關(guān)鍵在于每一步的選擇。

如果word1與word2的第一個(gè)字符相等，假設(shè)word1是hor、word2是hr，那么我們可以放心的排除掉兩個(gè)字符串的第一個(gè)字符，即EditDistance("hor", "hr")一定等于EditDistance("or", "r")：

此時(shí)我們得到了一個(gè)子問(wèn)題EditDistance("or", "r")，原始問(wèn)題EditDistance("hor", "hr")的值等于該子問(wèn)題。

真正有趣的是如果word1與word2的第一個(gè)字符不相等的情況，假設(shè)word1為“hor”，而word2為“ro”，此時(shí)根據(jù)該問(wèn)題的規(guī)則針對(duì)word1的第一個(gè)字符有三種操作：

1，在word1的第一個(gè)字符前新增(Insert)一個(gè)字符r，此時(shí)word1變?yōu)閞hor，由于此時(shí)word1 的第一個(gè)字符等于word2的第一個(gè)字符，可以放心的忽略掉，因此我們得到了子問(wèn)題EditDistance("hor","o")，由于執(zhí)行了一次新增操作，因此：

EditDistance("hor","ro")=EditDistance("hor","o")+1

2，將word1的第一個(gè)字符刪掉(Delete)，此時(shí)word1變?yōu)椤皁r”，我們得到了一個(gè)新的子問(wèn)題EditDistance("or","ro")，由于執(zhí)行了一次刪除操作，因此：

EditDistance("hor","ro")=EditDistance("or","ro")+1

3，將word1的第一個(gè)字符替換(Replace )為r，此時(shí)word1變?yōu)榱恕皉or”，由于word1的第一個(gè)字符等于word2的第一個(gè)字符，因此可以放心的忽略掉，我們得到了一個(gè)新的子問(wèn)題EditDistance("or","o")，由于執(zhí)行了一次刪除操作，因此：

EditDistance("hor","ro")=EditDistance("or","o")+1

根據(jù)題目要求，我們需要得到最小的編輯距離，因此：

EditDistance("hor","ro")=min(EditDistance("hor","o"),
EditDistance("or","ro"),
EditDistance("or","o"))+1

即：

可以看到，如果word1與word2的第一個(gè)字符如果不相等的話那么我們會(huì)得到三個(gè)子問(wèn)題，取這三個(gè)子問(wèn)題的最小值然后加1就是原始問(wèn)題的解。

現(xiàn)在我們找到了子問(wèn)題與原始問(wèn)題之間的依賴(lài)關(guān)系。

實(shí)際上，根據(jù)上述討論我們還可以進(jìn)一步擴(kuò)展從而得到完整的狀態(tài)空間樹(shù)。

從這棵樹(shù)中可以看到最小的編輯距離是2。

現(xiàn)在你應(yīng)該清楚的知道該怎樣我們是怎樣一步步將問(wèn)題不斷的分解為更小的子問(wèn)題，然后利用子問(wèn)題的解來(lái)得到原始問(wèn)題的解了。

自頂向下遞歸代碼

上圖中每個(gè)方框都是一個(gè)子問(wèn)題，決定一個(gè)子問(wèn)題的因素在于word1與word2當(dāng)前處理到了哪個(gè)位置，假設(shè)對(duì)word1處理到了第i個(gè)位置，對(duì)word2處理到了第j個(gè)位置，因此我們可以對(duì)問(wèn)題進(jìn)行定義：

intEditDistance(inti,intj);

該函數(shù)表示從i到word1的末尾形成的字符串與從j從word2的末尾形成的字符串的編輯距離。

因此如果調(diào)用該函數(shù)時(shí)我們應(yīng)該這樣使用：

EditDistance(0,0);

有了該定義與上述分析，你可以輕而易舉的寫(xiě)出這樣的遞歸代碼：

stringword1;
stringword2;

intEditDistance(inti,intj){
if(i==word1.length()&&j==word2.length())return0;
if(i==word1.length())returnword2.length()-j;
if(j==word2.length())returnword1.length()-i;

if(word1[i]==word2[j])returnEditDistance(i+1,j+1);
else{
returnmin(EditDistance(i+1,j+1),min(
EditDistance(i,j+1),
EditDistance(i+1,j)))+1;
}
}

我們將word1與word2聲明為全局變量，這樣你可以清楚的看到?jīng)Q定EditDistance函數(shù)值的因素只有這兩個(gè)參數(shù)i和j，i的取值為[0, word1.length()]，j的取值為[0, word2.length()]，也就是說(shuō)子問(wèn)題的個(gè)數(shù)只有(word1.length() + 1) * (word2.length() + 1) 個(gè)，上述遞歸代碼存在大量重復(fù)計(jì)算問(wèn)題，因此可以通過(guò)增加cache進(jìn)行優(yōu)化，這個(gè)改動(dòng)就留給大家啦。

接下來(lái)我們著手將自頂向下的遞歸代碼改為自底向上的動(dòng)態(tài)規(guī)劃代碼。

自底向上動(dòng)態(tài)規(guī)劃代碼

由于子問(wèn)題的個(gè)數(shù)只有(word1.length() + 1) * (word2.length() + 1) 個(gè)，因此可以定義一個(gè)相同大小的二維數(shù)組dp:

vector>dp(word1.length()+1,vector(word2.length()+1,0));

接下來(lái)我們要求解最小子問(wèn)題，最小子問(wèn)題就是上述遞歸代碼的遞歸出口：

if(i==word1.length()&&j==word2.length())return0;

該最小子問(wèn)題的解包含在了dp數(shù)組的初始化中。

接下來(lái)的子問(wèn)題是另外兩個(gè)遞歸出口：

if(i==word1.length())returnword2.length()-j;
if(j==word2.length())returnword1.length()-i;

我們可以簡(jiǎn)單的構(gòu)造出兩種情況下的所有i和j來(lái)初始化數(shù)組dp，即：

for(intj=word2.length()-1;j>=0;j--)
dp[word1.length()][j]=word2.length()-j;
for(inti=word1.length()-1;i>=0;i--)
dp[i][word2.length()]=word1.length()-i;

最后我們利用兩個(gè)for循環(huán)來(lái)構(gòu)造出所有的i和j，從而將遞歸函數(shù)的最后一部分：

if(word1[i]==word2[j])returnEditDistance(i+1,j+1);
else{
returnmin(EditDistance(i+1,j+1),min(
EditDistance(i,j+1),
EditDistance(i+1,j)))+1;
}

放置在for循環(huán)中，并將對(duì)遞歸函數(shù)的調(diào)用替換為對(duì)數(shù)組dp的讀寫(xiě)：

for(inti=word1.length()-1;i>=0;i--){
for(intj=word2.length()-1;j>=0;j--){
if(word1[i]==word2[j])
dp[i][j]=dp[i+1][j+1];
else
dp[i][j]=min(dp[i+1][j+1],min(dp[i][j+1],dp[i+1][j]))+1;
}
}

最終，完整的動(dòng)態(tài)規(guī)劃代碼為：

intminDistance(stringword1,stringword2){
vector>dp(word1.length()+1,vector(word2.length()+1,0));
for(intj=word2.length()-1;j>=0;j--)
dp[word1.length()][j]=word2.length()-j;
for(inti=word1.length()-1;i>=0;i--)
dp[i][word2.length()]=word1.length()-i;
for(inti=word1.length()-1;i>=0;i--){
for(intj=word2.length()-1;j>=0;j--){
if(word1[i]==word2[j])
dp[i][j]=dp[i+1][j+1];
else
dp[i][j]=min(dp[i+1][j+1],min(dp[i][j+1],dp[i+1][j]))+1;
}
}

returndp[0][0];
}

審核編輯：劉清