第九章 動態(tài)規(guī)劃part12

115.不同的子序列

但相對于剛講過 392.判斷子序列葵姥，本題 就有難度了 荷鼠，感受一下本題和 392.判斷子序列 的區(qū)別。
文章講解

思路

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i][j]：以i-1為結(jié)尾的s子序列中出現(xiàn)以j-1為結(jié)尾的t的個數(shù)為dp[i][j]榔幸。

2. 確定遞推公式
   這一類問題允乐，基本是要分析兩種情況

• s[i - 1] 與 t[j - 1]相等
• s[i - 1] 與 t[j - 1] 不相等
• 當s[i - 1] 與 t[j - 1]相等時矮嫉，dp[i][j]可以有兩部分組成。
  一部分是用s[i - 1]來匹配牍疏，那么個數(shù)為dp[i - 1][j - 1]蠢笋。即不需要考慮當前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]鳞陨。
  一部分是不用s[i - 1]來匹配昨寞，個數(shù)為dp[i - 1][j]。
• 為什么還要考慮 不用s[i - 1]來匹配厦滤，都相同了指定要匹配啊援岩。
  例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的掏导，但是字符串s也可以不用s[3]來匹配享怀，即用s[0]s[1]s[2]組成的bag。
  當然也可以用s[3]來匹配碘菜，即：s[0]s[1]s[3]組成的bag凹蜈。
• 當s[i - 1] 與 t[j - 1]不相等時，dp[i][j]只有一部分組成忍啸，不用s[i - 1]來匹配（就是模擬在s中刪除這個元素）仰坦，即：dp[i - 1][j]
  所以遞推公式為：dp[i][j] = dp[i - 1][j];

3. dp數(shù)組如何初始化
   從遞推公式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][j]的定義凿滤，不要憑感覺初始化妈橄。

• dp[i][0]表示什么呢？
  dp[i][0] 表示：以i-1為結(jié)尾的s可以隨便刪除元素翁脆，出現(xiàn)空字符串的個數(shù)眷蚓。
  那么dp[i][0]一定都是1，因為也就是把以i-1為結(jié)尾的s反番，刪除所有元素沙热，出現(xiàn)空字符串的個數(shù)就是1。
• 再來看dp[0][j]罢缸，dp[0][j]：空字符串s可以隨便刪除元素篙贸，出現(xiàn)以j-1為結(jié)尾的字符串t的個數(shù)。
  那么dp[0][j]一定都是0枫疆，s如論如何也變成不了t爵川。
• 最后就要看一個特殊位置了，即：dp[0][0] 應該是多少息楔。
  dp[0][0]應該是1寝贡，空字符串s扒披，可以刪除0個元素，變成空字符串t兔甘。

4. 確定遍歷順序
   從遞推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根據(jù)左上方和正上方推出來的谎碍。

5. 舉例推導dp數(shù)組
   以s："baegg"，t："bag"為例洞焙，推導dp數(shù)組狀態(tài)如下：

   
   
   image.png

class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i < len1; i++) dp[i][0] = 1;
        for(int j = 1; j < len2; j++) dp[0][j] = 0;
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}

583. 兩個字符串的刪除操作

本題和動態(tài)規(guī)劃：115.不同的子序列 相比，其實就是兩個字符串都可以刪除了拯啦，情況雖說復雜一些澡匪，但整體思路是不變的。
文章講解

思路

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i][j]：以i-1為結(jié)尾的字符串word1褒链，和以j-1位結(jié)尾的字符串word2唁情，想要達到相等，所需要刪除元素的最少次數(shù)甫匹。

2. 確定遞推公式

• 當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] 與 word2[j - 1]不相同的時候，有三種情況：
  • 情況一：刪word1[i - 1]兵迅，最少操作次數(shù)為dp[i - 1][j] + 1
  • 情況二：刪word2[j - 1]抢韭，最少操作次數(shù)為dp[i][j - 1] + 1
  • 情況三：同時刪word1[i - 1]和word2[j - 1]，操作的最少次數(shù)為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[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以遞推公式可簡化為：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
    從字面上理解 就是 當 同時刪word1[i - 1]和word2[j - 1]扯夭，dp[i][j-1] 本來就不考慮 word2[j - 1]了鳍贾，那么我在刪 word1[i - 1]胸遇，是不是就達到兩個元素都刪除的效果地啰，即 dp[i][j-1] + 1。

3. dp數(shù)組如何初始化
   從遞推公式中哼蛆，可以看出來构拳，dp[i][0] 和 dp[0][j]是一定要初始化的咆爽。
   dp[i][0]：word2為空字符串，以i-1為結(jié)尾的字符串word1要刪除多少個元素隐圾，才能和word2相同呢伍掀，很明顯dp[i][0] = i。
   dp[0][j]的話同理暇藏。

4. 確定遍歷順序
   從遞推公式 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]都是根據(jù)左上方蜜笤、正上方、正左方推出來的盐碱。
   所以遍歷的時候一定是從上到下把兔，從左到右沪伙，這樣保證dp[i][j]可以根據(jù)之前計算出來的數(shù)值進行計算。

5. 舉例推導dp數(shù)組
   

   以word1:"sea"县好，word2:"eat"為例围橡，推導dp數(shù)組狀態(tài)圖如下：
   image.png

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i <= len1; i++) dp[i][0] = i;
        for(int j = 0; j <= len2; j++) dp[0][j] = j;
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1]; //注意這里
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);               
                }
            }
        }
        return dp[len1][len2];
    }
}

動態(tài)規(guī)劃二

本題和 動態(tài)規(guī)劃：1143.最長公共子序列 基本相同，只要求出兩個字符串的最長公共子序列長度即可缕贡，那么除了最長公共子序列之外的字符都是必須刪除的翁授，最后用兩個字符串的總長度減去兩個最長公共子序列的長度就是刪除的最少步數(shù)。

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();

        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(char1[i - 1] == char2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1; 
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);               
                }
            }
        }
        return len1 + len2 - (2 * dp[len1][len2]);
    }
}

72. 編輯距離

最終我們迎來了編輯距離這道題目晾咪，之前安排題目都是為了 編輯距離做鋪墊收擦。
文章講解

思路

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i][j] 表示以下標i-1為結(jié)尾的字符串word1，和以下標j-1為結(jié)尾的字符串word2谍倦，最近編輯距離為dp[i][j]塞赂。

2. 確定遞推公式
   在確定遞推公式的時候，首先要考慮清楚編輯的幾種操作昼蛀，整理如下4種情況：

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

• if (word1[i - 1] == word2[j - 1]) 那么說明不用任何編輯宴猾，dp[i][j] 就應該是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

• if (word1[i - 1] != word2[j - 1])叼旋，此時就需要編輯了仇哆，如何編輯呢？

• 操作一：word1刪除一個元素送淆，那么就是以下標i - 2為結(jié)尾的word1 與 j-1為結(jié)尾的word2的最近編輯距離 再加上一個操作税产。
  即 dp[i][j] = dp[i - 1][j] + 1;

• 操作二：word2刪除一個元素，那么就是以下標i - 1為結(jié)尾的word1 與 j-2為結(jié)尾的word2的最近編輯距離 再加上一個操作偷崩。
  即 dp[i][j] = dp[i][j - 1] + 1;

• 怎么都是刪除元素辟拷，添加元素去哪了:
  word2添加一個元素，相當于word1刪除一個元素阐斜，例如 word1 = "ad" 衫冻，word2 = "a"，word1刪除元素'd' 和 word2添加一個元素'd'谒出，變成word1="a", word2="ad"隅俘， 最終的操作數(shù)是一樣的。

• 操作三：替換元素笤喳，word1替換word1[i - 1]为居，使其與word2[j - 1]相同，此時不用增刪加元素杀狡。
  可以回顧一下蒙畴，if (word1[i - 1] == word2[j - 1])的時候我們的操作 是 dp[i][j] = dp[i - 1][j - 1]
  那么只需要一次替換的操作，就可以讓 word1[i - 1] 和 word2[j - 1] 相同。
  所以 dp[i][j] = dp[i - 1][j - 1] + 1;

• 綜上膳凝，當 if (word1[i - 1] != word2[j - 1]) 時取最小的碑隆，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

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

• 再回顧一下dp[i][j]的定義：
  dp[i][j] 表示以下標i-1為結(jié)尾的字符串word1，和以下標j-1為結(jié)尾的字符串word2蹬音，最近編輯距離為dp[i][j]上煤。
• 那么dp[i][0] 和 dp[0][j] 表示什么呢？
  dp[i][0] ：以下標i-1為結(jié)尾的字符串word1著淆，和空字符串word2劫狠，最近編輯距離為dp[i][0]。
• 那么dp[i][0]就應該是i永部，對word1里的元素全部做刪除操作嘉熊，即：dp[i][0] = i;
• 同理dp[0][j] = j;

4. 確定遍歷順序
   從如下四個遞推公式：
   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]是依賴左方，上方和左上方元素的扬舒，如圖：
   image.png

5. 舉例推導dp數(shù)組
   以示例1為例，輸入：word1 = "horse", word2 = "ros"為例凫佛，dp矩陣狀態(tài)圖如下：

   
   
   image.png

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i <= len1; i++) dp[i][0] = i;
        for(int j = 0; j <= len2; j++) dp[0][j] = j;
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(char1[i - 1] == char2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j - 1]), dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
}

編輯距離總結(jié)篇

做一個總結(jié)吧

https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html