LeetCode 115.不同的子序列

題目鏈接：https://leetcode.cn/problems/distinct-subsequences/description/
文章鏈接：https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

思路

 * dp[i][j]：以i-1為結尾的s子序列中出現以j-1為結尾的t的個數為dp[i][j]。* 這一類問題，基本是要分析兩種情況* s[i - 1] 與 t[j - 1]相等* s[i - 1] 與 t[j - 1] 不相等* (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：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] = dp[i - 1][j - 1] + dp[i - 1][j];* (2)當s[i - 1] 與 t[j - 1]不相等時，dp[i][j]只有一部分組成，不用s[i - 1]來匹配（就是模擬在s中刪除這個元素），即：dp[i - 1][j]* 所以遞推公式為：dp[i][j] = dp[i - 1][j];

    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 i = 1; i <= len1 ; i++) {char t1 = s.charAt(i);for (int j = 1; j <= len2 ; j++) {char t2 = t.charAt(j);if (t1 == t2)dp[i][j] = dp[i-1][j-1] + dp[i-1][j];elsedp[i][j] = dp[i-1][j];}}return dp[len1][len2];}

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

題目鏈接：https://leetcode.cn/problems/delete-operation-for-two-strings/description/
文章鏈接：https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

 * 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] 與 word2[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[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以遞推公式可簡化為：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)

    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++) {char t1 = word1.charAt(i);for (int j = 1; j <= len2; j++) {char t2 = word2.charAt(j);if (t1 == t2)dp[i][j] = dp[i - 1][j - 1];elsedp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);}}return dp[len1][len2];}

LeetCode 72. 編輯距離

題目鏈接：https://leetcode.cn/problems/edit-distance/description/
文章鏈接：https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

 * dp[i][j] 表示以下標i-1為結尾的字符串word1，和以下標j-1為結尾的字符串word2，最近編輯距離為dp[i][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];* （2）if (word1[i - 1] != word2[j - 1])，此時就需要編輯了* 操作一：word1刪除一個元素，那么就是以下標i - 2為結尾的word1 與 j-1為結尾的word2的最近編輯距離 再加上一個操作。dp[i][j] = dp[i - 1][j] + 1;* 操作二：word2刪除一個元素，那么就是以下標i - 1為結尾的word1 與 j-2為結尾的word2的最近編輯距離 再加上一個操作。即 dp[i][j] = dp[i][j - 1] + 1;* 添加操作和刪除操作是一樣的，例如：word2添加一個元素，相當于word1刪除一個元素，例如 word1 = "ad" ，word2 = "a"，word1刪除元素'd' 和 word2添加一個元素'd'，變成word1="a", word2="ad"， 最終的操作數是一樣！* 操作三：替換元素，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;

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 = 1; i <= len1; i++) {dp[i][0] = i;}for (int j = 1; j <= len2; j++) {dp[0][j] = j;}for (int i = 1; i <= len1; i++) {char t1 = word1.charAt(i);for (int j = 1; j <= len2; j++) {char t2 = word2.charAt(j);if (t1 == t2)dp[i][j] = dp[i - 1][j - 1];elsedp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);}}return dp[len1][len2];}