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

1143.最長公共子序列

體會一下本題和 718. 最長重復(fù)子數(shù)組 的區(qū)別
文章講解

題目
給定兩個字符串 text1 和 text2，返回這兩個字符串的最長公共子序列的長度。

一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列。

若這兩個字符串沒有公共子序列，則返回 0。

思路
繼續(xù)動規(guī)五部曲分析如下：

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i][j]：長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列為dp[i][j]
   這樣定義是為了后面代碼實現(xiàn)方便，其實就是簡化了dp數(shù)組第一行和第一列的初始化邏輯。

2. 確定遞推公式

• 兩大情況： text1[i - 1] 與 text2[j - 1]相同，text1[i - 1] 與 text2[j - 1]不相同
• 如果text1[i - 1] 與 text2[j - 1]相同，那么找到了一個公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
• 如果text1[i - 1] 與 text2[j - 1]不相同，那就看看text1[0, i - 2]與text2[0, j - 1]的最長公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長公共子序列，取最大的。
  即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

3. dp數(shù)組如何初始化
   先看看dp[i][0]應(yīng)該是多少呢？
   test1[0, i-1]和空串的最長公共子序列自然是0，所以dp[i][0] = 0;
   同理dp[0][j]也是0。
   其他下標都是隨著遞推公式逐步覆蓋，初始為多少都可以，那么就統(tǒng)一初始為0。

4. 確定遍歷順序
   從遞推公式，可以看出，有三個方向可以推出dp[i][j]，如圖：

   
   
   image.png
   
   

   那么為了在遞推的過程中，這三個方向都是經(jīng)過計算的數(shù)值，所以要從前向后，從上到下來遍歷這個矩陣。

5. 舉例推導(dǎo)dp數(shù)組
   以輸入：text1 = "abcde", text2 = "ace" 為例，dp狀態(tài)如圖：

image.png

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(text1.charAt(i - 1) == text2.charAt(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 dp[len1][len2];
    }
}

什么時候使用 i <= text1.length() 和 i < text1.length()

• 使用 i <= text1.length() 的情況：
  當(dāng)你在 DP 表中額外添加了一行和一列（通常初始化為 0），用來處理邊界情況（即空字符串的情況），此時循環(huán)的范圍需要包括這行這列，即 i 從 1 開始，直到 text1.length()（包含）。
• 使用 i < text1.length() 的情況：
  當(dāng)你沒有額外添加這一行和一列，而是直接在 DP 表中使用索引 0 代表第一個字符，索引 text1.length() - 1 代表最后一個字符時，此時循環(huán)的范圍是 i 從 0 開始，直到 text1.length() - 1（不包含 text1.length()）。

1035.不相交的線

其實本題和 1143.最長公共子序列 是一模一樣的，大家嘗試自己做一做。
文章講解

思路
繪制一些連接兩個數(shù)字 A[i] 和 B[j] 的直線，只要 A[i] == B[j]，且直線不能相交！
直線不能相交，這就是說明在字符串A中 找到一個與字符串B相同的子序列，且這個子序列不能改變相對順序，只要相對順序不改變，鏈接相同數(shù)字的直線就不會相交。

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[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 dp[len1][len2];
    }
}

53. 最大子序和

這道題我們用貪心做過，這次 再用dp來做一遍
文章講解

動規(guī)五部曲如下：

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i]：包括下標i（以nums[i]為結(jié)尾）的最大連續(xù)子序列和為dp[i]。

2. 確定遞推公式
   dp[i]只有兩個方向可以推出來：
   dp[i - 1] + nums[i]，即：nums[i]加入當(dāng)前連續(xù)子序列和
   nums[i]，即：從頭開始計算當(dāng)前連續(xù)子序列和
   一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

3. dp數(shù)組如何初始化
   從遞推公式可以看出來dp[i]是依賴于dp[i - 1]的狀態(tài)，dp[0]就是遞推公式的基礎(chǔ)。
   dp[0]應(yīng)該是多少呢?
   根據(jù)dp[i]的定義，很明顯dp[0]應(yīng)為nums[0]即dp[0] = nums[0]。

4. 確定遍歷順序
   遞推公式中dp[i]依賴于dp[i - 1]的狀態(tài)，需要從前向后遍歷。

5. 舉例推導(dǎo)dp數(shù)組
   以示例一為例，輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]，對應(yīng)的dp狀態(tài)如下：

   
   
   image.png

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = res > dp[i] ? res: dp[i];
        }
        return res;
    }
}

392.判斷子序列

這道題目算是 編輯距離問題 的入門題目（畢竟這里只是涉及到減法），慢慢的，后面就要來解決真正的 編輯距離問題了
文章講解

思路
動態(tài)規(guī)劃五部曲分析如下：

1. 確定dp數(shù)組（dp table）以及下標的含義
   dp[i][j] 表示以下標i-1為結(jié)尾的字符串s，和以下標j-1為結(jié)尾的字符串t，相同子序列的長度為dp[i][j]。

2. 確定遞推公式
   在確定遞推公式的時候，首先要考慮如下兩種操作，整理如下：

• if (s[i - 1] == t[j - 1])
  t中找到了一個字符在s中也出現(xiàn)了
• if (s[i - 1] != t[j - 1])
  相當(dāng)于t要刪除元素，繼續(xù)匹配
• if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因為找到了一個相同的字符，相同子序列長度自然要在dp[i-1][j-1]的基礎(chǔ)上加1（如果不理解，在回看一下dp[i][j]的定義）
• if (s[i - 1] != t[j - 1])，此時相當(dāng)于t要刪除元素，t如果把當(dāng)前元素t[j - 1]刪除，那么dp[i][j] 的數(shù)值就是 看s[i - 1]與 t[j - 2]的比較結(jié)果了，即：dp[i][j] = dp[i][j - 1];
• 其實這里 大家可以發(fā)現(xiàn)和 1143.最長公共子序列 的遞推公式基本那就是一樣的，區(qū)別就是 本題 如果刪元素一定是字符串t，而 1143.最長公共子序列 是兩個字符串都可以刪元素。

3. dp數(shù)組如何初始化
   從遞推公式可以看出dp[i][j]都是依賴于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
   這里大家已經(jīng)可以發(fā)現(xiàn)，在定義dp[i][j]含義的時候為什么要表示以下標i-1為結(jié)尾的字符串s，和以下標j-1為結(jié)尾的字符串t，相同子序列的長度為dp[i][j]。
   

   因為這樣的定義在dp二維矩陣中可以留出初始化的區(qū)間，如圖：
   image.png

4. 確定遍歷順序
   同理從遞推公式可以看出dp[i][j]都是依賴于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍歷順序也應(yīng)該是從上到下，從左到右

5. 舉例推導(dǎo)dp數(shù)組
   以示例一為例，輸入：s = "abc", t = "ahbgdc"，dp狀態(tài)轉(zhuǎn)移圖如下：

   
   
   image.png

class Solution {
    public boolean isSubsequence(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        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] + 1;
                }else{
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        if(dp[len1][len2] == len1) return true;
        else return false;
    }
}

用雙指針似乎更簡單，練習(xí)一下

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sp = 0;
        int tp = 0;
        while(sp < s.length() && tp < t.length()){
            if(s.charAt(sp) == t.charAt(tp)) sp++;
            tp++;
        }
        if(sp == s.length()) return true;
        else return false;
    }
}