代码随想录算法训练营 | 115.不同的子序列，583. 两个字符串的删除操作，72. 编辑距离

115.不同的子序列
题目链接：115.不同的子序列
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰不同的子序列
日期：2024-10-18

想法：dp[i][j]表示以s[i -1],t[j - 1]结尾的s,t自学列中满足s的子序列为t的个数，如果s[i -1],t[j - 1]相等，那么个数应该跟双方上一个结尾状态dp[i - 1][j - 1]一样，但由于还有像dogg和dog这种情况，还需要t当前的序列跟s的上一个长度序列进行计算，即dp[i - 1][j]，这个状态也要考虑，如果不等就比较简单只用考虑s上一个状态对应此时的t就行了即dp[i - 1][j];初始化dp[0][j]（j > 0）显然不会有空的s满足不空的t，全为0，dp[i][0]（i > 0）s的子序列都可以删减到空，有一个能满足，dp[i][0] = 1,dp[0][0]考虑到空s删除0个字符得到空t，可以视为1，也可以从如果s[0] = t[0]得到dp[1][1] = 1推出dp[0][0]要为1.
Java代码如下：

class Solution {
    public int numDistinct(String s, String t) {
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for(int i = 0; i <= s.length(); i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i <= s.length(); i++) {
            for(int j = 1; j <= t.length(); j++) {
                if(charS[i - 1] == charT[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.length()][t.length()];
    }
}

583. 两个字符串的删除操作
题目链接：583. 两个字符串的删除操作
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰两个字符串的删除操作
日期：2024-10-18

想法：思路1：dp[i][j]以i-1,j-1为结尾的字符串word1,word2，想要达到相等，所需要删除元素的最少次数。当word1[i - 1]，word2[j - 1]相等时，这两个就不用删了，那么次数跟上一次的相等，即dp[i - 1][j - 1],不等时，就要考虑是删word1还是word2，还是两个一起，分别是dp[i - 1][j] + 1，dp[i][j - 1] + 1，dp[i - 1][j - 1] + 2。初始化显然dp[i][0] = i，dp[0][j] = j，有多少字符删多少到空。
Java代码如下：
思路2：找word1,word2的最长子序列长度，然后减。

//思路1
class Solution {
    public int minDistance(String word1, String word2) {
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 0; i <= word1.length(); i++) dp[i][0] = i;
        for(int i = 0; i <= word2.length(); i++) dp[0][i] = i;

        for(int i = 1; i <= word1.length(); i++) {
            for(int j = 1; j <= word2.length(); j++) {
                if(char1[i - 1] == char2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

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

        for(int i = 1; i < word1.length() + 1; i++) {
            for(int j = 1; j < word2.length() + 1; 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 word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
    }
}

72. 编辑距离
题目链接：72. 编辑距离
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰编辑距离
日期：2024-10-18

想法：dp[i][j]表示以word1[i - 1]word2[j - 1]结尾的word1,word2的子序列从1变到2最少步骤；word1[i - 1]word2[j - 1]相等，这个位置不用变化，保持前个位置的次数就行即dp[i - 1][j - 1]，不同的时候，考虑改变的操作有三种，增删改，word1增可以等效于word2删一个（a, ad）即dp[i][j - 1] + 1;word1删，dp[i - 1][j] + 1；改，将word1[i - 1]，word2[j - 1]改为相等，在前个位置的次数基础上再加一就行了即dp[i - 1][j - 1] + 1，最后看这三种那种次数最少。初始化，都是有多少位删（加）到多少位。
Java代码如下：

class Solution {
    public int minDistance(String word1, String word2) {
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 0; i <= word1.length(); i++) dp[i][0] = i;
        for(int j = 0; j <= word2.length(); j++) dp[0][j] = j;

        for(int i = 1; i <= word1.length(); i++) {
            for(int j = 1; j <= word2.length(); j++) {
                if(char1[i - 1] == char2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}