? ? ? ?大家好，今天我們還是繼續我們的動態規劃章節，可能有的朋友已經開始厭倦了說為什么動態規劃怎么這么多題目，大家可以想想我們前面其實刷過好幾種類型的動態規劃的經典題目比如說各式各樣的背包問題當然包括0-1背包，完全背包，大家也知道這兩種背包問題的差異就在于物品是否可以選擇多次，后面我們還刷了打家劫舍問題，當然還有比較難的買股票的最佳時期問題，前天我們也開始我們的子序列問題，那我們今天還有一種比較重要的問題就是編輯距離問題，那我們就一起走進我們今天的題目。

第一題對應力扣編號為115的題目不同的子序列

? ? ? ?其實大家看到這道題的時候大家應該會想起我們昨天刷過一道題目叫做判斷子序列，其實我可以告訴大家，這道題要比那道題難一些，我們來看看這道題的題目要求：

? ? ? ? 看完題目我們明白了，其實跟那道題有點類似的地方就是都涉及到了子序列的問題，但是這道題我們是需要求出s的子序列中t出現的次數，這個其實就有難度了，當然我們也知道本題目應該是可以使用動態規劃的思路來解題的，那我們就嘗試使用動規五部曲來解決這道題目：

? ? ? ?第一步確定dp數組以及下標的含義，dp[i][j]：以i-1為結尾的s子序列中出現以j-1為結尾的t的個數為dp[i][j]。我們前面有道題說過為了初始化方便我們是i-1而不是i。

? ? ? ? 第二步確定遞推公式，感覺這個就有難度了，其實我們做的題目多了就會有感覺，我們應該還是需要看對應位置上的元素是否相等，第一種情況是s[i - 1] 與 t[j - 1]相等，第二種情況是s[i - 1] 與 t[j - 1] 不相等，當s[i - 1] 與 t[j - 1]相等時，dp[i][j]可以有兩部分組成。一部分是用s[i - 1]來匹配，那么個數為dp[i - 1][j - 1]。即不需要考慮當前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。還有一種情況就是一部分是不用s[i - 1]來匹配，個數為dp[i - 1][j]。另一種情況就是s[i - 1] 與 t[j - 1]不相等時，我們這時候其實相當于dp[i][j]只有一部分組成，不用s[i - 1]來匹配（就是模擬在s中刪除這個元素），即：dp[i - 1][j]。

? ? ? ?第三步是dp數組的初始化，從遞推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是從上方和左上方推導而來，那么 dp[i][0] 和dp[0][j]是一定要初始化的。那其實也很明顯，我們的dp[i][0]應該初始化為1，而且我們的dp[0][j]應該初始化為0，但是大家要注意我們dp[0][0]應該是初始化為1，因此我們dp[0][j]的初始化應該是從1開始初始化為0.

? ? ? ?第四步就是遍歷順序的確定，其實很明顯就是從前往后，這個就無需多說了，其實嚴格來說應該是左上方和正上方推出來的。

? ? ? 根據以上分析我們可以給出代碼：

class Solution {
public:int numDistinct(string s, string t) {//初始化dp數組vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));//dp數組初始化for (int i = 0; i <= s.size(); ++i) dp[i][0] = 1;for (int j = 1; j <= t.size(); ++j) dp[0][j] = 0;for (int i = 1; i <= s.size(); ++i){for (int j = 1; j <= t.size(); ++j){//如果相同存在兩種情況第一種用最后一個元素第二種不用最后一個元素if (s[i - 1] == t[j - 1]){dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else{//如果不相等就得模擬刪除當前最后一個元素dp[i][j] = dp[i - 1][j];}}}return dp[s.size()][t.size()];}
};

? ? ? ?其實本題的難點就在于理解狀態轉移方程，我們本題的dp數組的含義其實還是比較抽象的，我們要比較對應位置的元素是否相等，如果相等的話我們應該如何操作，如果不相等的話我們應該如何操作。其實我一想了好久才大致明白我們的狀態轉移，我開始也思考了為什么我們不考慮用不用t[j-1]后來發現是因為我沒有仔細審題，題目問的是s中有多少個t，所以重點考慮的應該是s[i-1]，還有如果我們對應的元素不相等，其實我們相當于模擬刪除s里面的s[i-1]因此我們這里應該是dp[i-1][j]，相等的話我們則不需要考慮兩個字符串的最后一個元素，但是不相等的話我們的確是需要考慮。這點大家要多思考。

第二題對應力扣編號為583的題目兩個字符串的刪除操作

? ? ? ? 我們來到今天的第二題，第一題真給我差點整不會了，大家務必要仔細思考一下，我們來看今天的第二題是什么意思：

? ? ? ?其實題目理解起來并不算難，就是我們要使得兩個字符串相同我們就需要進行增加刪除操作，我們需要求我們最少的操作數是多少，我們還是得使用動規五部曲的思路來解決這道題目：

? ? ? ? 第一步確定dp數組以及下標的含義，我們應該是dp[i][j]：以i-1為結尾的字符串word1，和以j-1位結尾的字符串word2，想要達到相等，所需要刪除元素的最少次數。這個定義起來其實不難，但是難的應該是遞推公式。

? ? ? ? 第二步確定遞推公式，同樣我們還是得考慮對應位置的元素是否相等，也就是當word1[i - 1] 與 word2[j - 1]相同的時候，和當word1[i - 1] 與 word2[j - 1]不相同的時候，先來看第一種情況就是對應位置元素相同的時候，當word1[i - 1] 與 word2[j - 1]相同的時候，dp[i][j] = dp[i - 1][j - 1]，這個其實好理解，對應位置相同我們這里的元素無需操作只需看前面即可，但是比較難的是第二種情況，這個其實又有好幾種情況，情況一：刪word1[i - 1]，最少操作次數為dp[i - 1][j] + 1，刪word2[j - 1]，最少操作次數為dp[i][j - 1] + 1，同時刪word1[i - 1]和word2[j - 1]，操作的最少次數為dp[i - 1][j - 1] + 2，那最后當然是取最小值，所以當word1[i - 1] 與 word2[j - 1]不相同的時候，遞推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1})，其實這里想一次性想得很全面我個人感覺是比較難的。

? ? ? ? 第三步dp數組的初始化，從遞推公式中，可以看出來，dp[i][0] 和 dp[0][j]是一定要初始化的。但其實似乎又不難理解，dp[i][0]：word2為空字符串，以i-1為結尾的字符串word1要刪除多少個元素，才能和word2相同呢，很明顯dp[i][0] = i。dp[0][j]的話同理，不應該是刪除j個因此dp[0][j]=j，這樣我們的初始化就完成了。

? ? ? ? 第四步確定遍歷順序，這個其實也毫無疑問，從遞推公式 dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根據左上方、正上方、正左方推出來的。

? ? ? ? 那通過以上分析我們就可以嘗試給出本題的解題代碼：

class Solution {
public:int minDistance(string word1, string word2) {//定義dp數組vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1));//dp數組的初始化for (int i = 0; i <= word1.size(); ++i) dp[i][0] = i;for (int j = 0; j <= word2.size(); ++j) dp[0][j] = j; for (int i = 1; i <= word1.size(); ++i){for (int j = 1; j <= word2.size(); ++j){if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else{dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));}}}return dp[word1.size()][word2.size()];}
};

? ? ? ? 其實本題的難點在于考慮的情況是否周全，還是思路要理清。接下來就是重頭戲編輯距離題目，我們這道題目就分享到這里。

第三題對應力扣編號為72的題目編輯距離

? ? ? ? 在刷題過程中我似乎記得我們前面刷的題都是為這個題目服務的，其實上一個題目我們只涉及到了字符串的刪除沒有涉及到替換添加等操作，那我們就一起來看看這道題目的具體要求：

? ? ? ?我們其實是求將前面的字符串變成后面字符串的的最少操作數，當然本題目我們可以進行替換刪除插入操作，而我們前面的題目只能進行刪除操作，那我們需要考慮的情況可能就更多了，我們就使用動規五部曲來解決一下這道題目：

? ? ? ?第一步就是確定?確定dp數組以及下標的含義，其實這個似乎不難，我們完全有經驗，dp[i][j] 表示以下標i-1為結尾的字符串word1，和以下標j-1為結尾的字符串word2，最近編輯距離為dp[i][j]。跟我們以前的題目定義dp數組的思路是完全類似的。

? ? ? ?第二步就是確定遞推公式，這個或許有難度，這個題如果我們要操作的話我們就必須考慮插入刪除替換等各種操作，如果對應元素相同那么就不需要任何的操作，但是如果不同的話就麻煩了，其實有如下幾個操作，操作一：word1刪除一個元素，那么就是以下標i - 2為結尾的word1 與 j-1為結尾的word2的最近編輯距離 再加上一個操作。操作二：word2刪除一個元素，那么就是以下標i - 1為結尾的word1 與 j-2為結尾的word2的最近編輯距離 再加上一個操作。這里就有問題了為什么都是刪除元素為什么沒有添加元素的操作，其實大家可以變相思考一下，我word2添加一個元素，相當于word1刪除一個元素，比如說word1 = "ad", word2 = "a",那我word1刪除一個"d"變成"a",與word2添加一個"d",變成"ad"的最后的操作數應該是一樣的，操作三：替換元素，這個其實word1替換word1[i - 1]，使其與word2[j - 1]相同,?那么只需要一次替換的操作，就可以讓 word1[i - 1] 和 word2[j - 1] 相同,因此這時候dp[i][j] = dp[i-1][j - 1] +1，那這樣我們的遞推公式就知道了，就是分為對應元素相等跟不相等的情況。

? ? ? 第三步就是dp數組的初始化，應該重點思考dp[i][0] 和 dp[0][j] 表示什么？其實也不難，dp[i][0]就應該是i，對word1里的元素全部做刪除操作，即：dp[i][0] = i; 同理dp[0][j] = j; 這個其實我們上一道題目就涉及到了。

? ? ? 第四步就是遍歷順序，其實我們也不多說了跟上一道題目是完全一樣的。

? ? ? 這樣經過我們的分析我們就給出本題的解題代碼：

class Solution {
public:int minDistance(string word1, string word2) {//初始化dp數組vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));//dp數組初始化for (int i = 0; i <= word1.size(); ++i) dp[i][0] = i;for (int j = 0; j <= word2.size(); ++j) dp[0][j] = j;for (int i = 1; i <= word1.size(); ++i){for (int j = 1; j <= word2.size(); ++j){if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));}}return dp[word1.size()][word2.size()];}
};

? ? ? ? 這道題目很有趣，完全就是動態規劃的典型例題，大家一定要把這道題目掌握扎實，我感覺好多公司面試都會考察這道題目，其實我給大家一個總結大家重點首先理解dp數組，其次搞清楚我們需要什么樣的操作就可以了，有的我們只可以進行刪除操作，有的我們增刪改查都可以，而且大家要明白每一種操作我們的狀態轉移方程應該如何表示就可以，其實我們前面的幾道題都是為了編輯距離這道題目服務的，可是說是絕殺。大家務必學明白！！

今日總結

? ? ? ? 我們即將到達動態規劃的終結篇了，我們還有單調棧跟圖論我們的訓練營就結束了，大家收獲一定是滿滿的，我們在眾多章節收獲了很多，大家需要二刷甚至三刷才可以，重要的是理解思想，多去思考多去嘗試就可以，我們今天的分享就到這里，大家明天見！

? ? ? ?