日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

大家好，我是小風哥。

超過10余年行業(yè)經(jīng)驗，技術領先，服務至上的經(jīng)營模式，全靠網(wǎng)絡和口碑獲得客戶，為自己降低成本，也就是為客戶降低成本。到目前業(yè)務范圍包括了：成都做網(wǎng)站、成都網(wǎng)站設計、成都外貿(mào)網(wǎng)站建設，成都網(wǎng)站推廣，成都網(wǎng)站優(yōu)化，整體網(wǎng)絡托管，微信小程序開發(fā)，微信開發(fā)，成都App制作，同時也可以讓客戶的網(wǎng)站和網(wǎng)絡營銷和我們一樣獲得訂單和生意！

這是動態(tài)規(guī)劃主題的第三篇，本篇的題目非常經(jīng)典，幾乎是面試必備，即，編輯距離問題，edit distance；

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

• 新增一個字符
• 刪除一個字符
• 替換一個字符

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

1. 將word1中的第一個字符h替換為字符r：horse -> rorse，此時word1變?yōu)閞orse，word1與word2前兩個字符相等
2. 將word1中的第三個字符r刪掉：rorse -> rose，此時word1變?yōu)閞ose，word1與word2的前三個字符相等
3. 將word1中的最后一個字符刪掉：rose -> ros，此時word1與word2相等。

想一想該怎樣用動態(tài)規(guī)劃解決這個問題。

選擇與子問題

和之前的題目一樣，你首先應該找出子問題是什么，子問題與原始問題的依賴關系是什么。

找出子問題的關鍵在于每一步的選擇。

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

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

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

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

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

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

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

3，將word1的第一個字符替換(Replace )為r，此時word1變?yōu)榱恕皉or”，由于word1的第一個字符等于word2的第一個字符，因此可以放心的忽略掉，我們得到了一個新的子問題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的第一個字符如果不相等的話那么我們會得到三個子問題，取這三個子問題的最小值然后加1就是原始問題的解。

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

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

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

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

自頂向下遞歸代碼

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

int EditDistance(int i, int j);

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

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

EditDistance(0, 0);

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

string word1;
string word2;

int EditDistance(int i, int j) {
  if (i == word1.length() && j == word2.length()) return 0;
  if (i == word1.length()) return word2.length() - j;
  if (j == word2.length()) return word1.length() - i;

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

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

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

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

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

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

接下來我們要求解最小子問題，最小子問題就是上述遞歸代碼的遞歸出口：

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

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

接下來的子問題是另外兩個遞歸出口：

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

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

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

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

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

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

for (int i = word1.length() - 1; i >= 0; i--) {
  for (int j = 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;
  }
}

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

int minDistance(string word1, string word2) {
  vector>dp(word1.length() + 1, vector(word2.length() + 1, 0));
  for (int j = word2.length() - 1; j >= 0; j--)
    dp[word1.length()][j] = word2.length() - j;
  for (int i = word1.length() - 1; i >= 0; i--)
    dp[i][word2.length()] = word1.length() - i;
  for (int i = word1.length() - 1; i >= 0; i--) {
    for (int j = 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;
    }
  }

  return dp[0][0];
}

標題名稱：徹底理解動態(tài)規(guī)劃：編輯距離
文章地址：http://m.5511xx.com/article/cdipjdh.html