成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

徹底理解動態規劃:編輯距離

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

大家好,我是小風哥。

這是動態規劃主題的第三篇,本篇的題目非常經典,幾乎是面試必備,即,編輯距離問題,edit distance;

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

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

假如word1是"horse",word2是“ros”,那么你的程序需要返回3,也就是說將word1轉為word2至少需要三個步驟:

  1. 將word1中的第一個字符h替換為字符r:horse -> rorse,此時word1變為rorse,word1與word2前兩個字符相等
  2. 將word1中的第三個字符r刪掉:rorse -> rose,此時word1變為rose,word1與word2的前三個字符相等
  3. 將word1中的最后一個字符刪掉:rose -> ros,此時word1與word2相等。

想一想該怎樣用動態規劃解決這個問題。

選擇與子問題

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

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

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

圖片

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

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

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

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

2,將word1的第一個字符刪掉(Delete),此時word1變為“or”,我們得到了一個新的子問題EditDistance("or","ro"),由于執行了一次刪除操作,因此:

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

3,將word1的第一個字符替換(Replace )為r,此時word1變為了“ror”,由于word1的第一個字符等于word2的第一個字符,因此可以放心的忽略掉,我們得到了一個新的子問題EditDistance("or","o"),由于執行了一次刪除操作,因此:

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

根據題目要求,我們需要得到最小的編輯距離,因此:

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

即:

圖片

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

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

實際上,根據上述討論我們還可以進一步擴展從而得到完整的狀態空間樹。

圖片

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

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

自頂向下遞歸代碼

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

int EditDistance(int i, int j);

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

因此如果調用該函數時我們應該這樣使用:

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聲明為全局變量,這樣你可以清楚的看到決定EditDistance函數值的因素只有這兩個參數i和j,i的取值為[0, word1.length()],j的取值為[0, word2.length()],也就是說子問題的個數只有(word1.length() + 1) * (word2.length() + 1) 個,上述遞歸代碼存在大量重復計算問題,因此可以通過增加cache進行優化,這個改動就留給大家啦。

接下來我們著手將自頂向下的遞歸代碼改為自底向上的動態規劃代碼。


自底向上動態規劃代碼

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

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

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

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

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

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

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

我們可以簡單的構造出兩種情況下的所有i和j來初始化數組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循環來構造出所有的i和j,從而將遞歸函數的最后一部分:

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循環中,并將對遞歸函數的調用替換為對數組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;
}
}

最終,完整的動態規劃代碼為:

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


責任編輯:武曉燕 來源: 碼農的荒島求生
相關推薦

2022-12-29 08:12:51

動態規劃profit

2022-12-11 10:37:15

動態規劃字符串超序列

2021-09-06 06:31:40

理解動態規劃

2021-05-13 08:55:33

Android架構功能

2025-02-13 09:06:27

2019-11-07 10:37:36

CookieSessionToken

2020-03-03 14:15:49

Redis持久化數據庫

2019-06-11 14:45:25

2019-01-09 08:31:07

2024-03-15 08:23:26

異步編程函數

2019-12-10 13:55:10

Go指針存儲

2023-12-28 10:39:57

數組節點數據結構

2022-10-24 08:08:27

閉包編譯器

2021-12-27 09:33:12

內存泄漏程序

2021-10-15 09:53:12

工具

2023-10-27 11:21:20

C語言Multics語言

2024-04-29 08:15:07

I/OCPU密集型

2021-12-06 11:19:47

語言指針內存

2022-02-28 11:10:42

ZGCG1收集器

2022-01-06 14:25:24

C語言指針內存
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板: 欧美一区二区黄 | 男女午夜激情视频 | 国产精品一区二区久久久久 | 亚洲国产一区二区三区在线观看 | 一区二区日韩 | 国产激情一区二区三区 | 国产高清精品一区二区三区 | 一区二区三区免费网站 | 亚洲精品久 | 国产精品久久国产精品 | 久久精品亚洲国产 | 国内自拍偷拍视频 | 久久精品欧美一区二区三区不卡 | 亚洲另类视频 | 91精品国产乱码久久久久久久久 | 永久免费视频 | 亚洲精品一区久久久久久 | 一级黄色毛片 | 日韩精品在线一区 | 亚洲一区二区视频 | 91在线精品一区二区 | 成人午夜精品 | 懂色av色香蕉一区二区蜜桃 | 久久久久久国产 | 国产高清av免费观看 | 国产精品久久免费观看 | av手机在线| 超碰日本 | 国产美女一区二区 | 久久久久久国产精品免费免费 | 先锋资源在线 | 91国内精品| h视频在线看| 亚洲午夜视频在线观看 | 国产日韩欧美在线观看 | 亚洲bt 欧美bt 日本bt | 亚洲在线视频 | 成人在线免费视频 | 国产精品成人一区二区 | 欧美一级全黄 | 日本亚洲欧美 |