確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串word1，和以下標(biāo)j-1為結(jié)尾的字符串word2，最近編輯距離為dp[i][j]。

確定遞推公式

在確定遞推公式的時(shí)候，首先要考慮清楚編輯的幾種操作，整理如下：

if (word1[i - 1] == word2[j - 1]) 不操作

if (word1[i - 1] != word2[j - 1]) 增 | 刪 | 換

也就是如上四種情況。

if (word1[i - 1] == word2[j - 1]) 那么說(shuō)明不用任何編輯，dp[i][j] 就應(yīng)該是 dp[i - 1][j- 1]，即dp[i][j] = dp[i - 1][j - 1];

if (word1[i - 1] != word2[j - 1])，此時(shí)就需要編輯了，如何編輯呢？

操作一：word1增加一個(gè)元素，使其word1[i - 1]與word2[j - 1]相同，那么就是以下標(biāo)i-2為結(jié)尾的word1 與 i-1為結(jié)尾的word2的最近編輯距離 加上一個(gè)增加元素的操作。

即 dp[i][j] = dp[i - 1][j] + 1;

操作二：word2添加一個(gè)元素，使其word1[i - 1]與word2[j - 1]相同，那么就是以下標(biāo)i-1為結(jié)尾的word1 與j-2為結(jié)尾的word2的最近編輯距離 加上一個(gè)增加元素的操作。

即 dp[i][j] = dp[i][j - 1] + 1;

這里有同學(xué)發(fā)現(xiàn)了，怎么都是添加元素，刪除元素去哪了。

word2添加一個(gè)元素，相當(dāng)于word1刪除一個(gè)元素，例如 word1 = “ad” ，word2 = “a”，word2添加一個(gè)元素d，也就是相當(dāng)于word1刪除一個(gè)元素d，操作數(shù)是一樣！

操作三：替換元素，word1替換word1[i - 1]，使其與word2[j -1]相同，此時(shí)不用增加元素，那么以下標(biāo)i-2為結(jié)尾的word1 與 j-2為結(jié)尾的word2的最近編輯距離 加上一個(gè)替換元素的操作。

即 dp[i][j] = dp[i - 1][j - 1] + 1;

綜上，當(dāng) if (word1[i - 1] != word2[j - 1]) 時(shí)取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

dp數(shù)組如何初始化

在回顧一下dp[i][j]的定義。

dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串word1，和以下標(biāo)j-1為結(jié)尾的字符串word2，最近編輯距離為dp[i][j]。

那么dp[i][0] 和 dp[0][j] 表示什么呢？

dp[i][0] ：以下標(biāo)i-1為結(jié)尾的字符串word1，和空字符串word2，最近編輯距離為dp[i][0]。

那么dp[i][0]就應(yīng)該是i，對(duì)word1里的元素全部做刪除操作，即：dp[i][0] = i;

同理dp[0][j] = j;

確定遍歷順序

從如下四個(gè)遞推公式：

dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j] = dp[i][j - 1] + 1
dp[i][j] = dp[i - 1][j] + 1
可以看出dp[i][j]是依賴(lài)左方，上方和左上方元素的，如圖：

舉例推導(dǎo)dp數(shù)組

以示例1，輸入：word1 = “horse”, word2 = "ros"為例，dp矩陣狀態(tài)圖如下：

class Solution { public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));for(int ii=0;ii<=word1.size();ii++) dp[ii][0]=ii;for(int jj=0;jj<=word2.size();jj++) dp[0][jj]=jj;for(int ii=1;ii<=word1.size();ii++){for(int jj=1;jj<=word2.size();jj++){if(word1[ii-1]==word2[jj-1]) dp[ii][jj]=dp[ii-1][jj-1];else dp[ii][jj]=min({dp[ii-1][jj]+1,dp[ii-1][jj-1]+1,dp[ii][jj-1]+1});}}return dp[word1.size()][word2.size()];} };

總結(jié)

以上是生活随笔為你收集整理的绝杀编辑距离的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。