代码随想录训练营第四十五天| 115.不同的子序列 583. 两个字符串的删除操作 72. 编辑距离 编辑距离总结篇

标签：四十五天 删除 int 随想录 编辑 word1 word2 字符串 dp

115.不同的子序列

题目链接：115. 不同的子序列 - 力扣（LeetCode）

讲解链接：代码随想录

 hard 确实不好直接说出来

粘一下思路：（引自代码随想录）

确定dp数组（dp table）以及下标的含义

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

为什么i-1，j-1 这么定义卡哥在 718. 最长重复子数组 (opens new window)中做了详细的讲解。

确定递推公式

这一类问题，基本是要分析两种情况

• 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]来匹配，都相同了指定要匹配啊。

例如： 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];

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]

所以递推公式为：dp[i][j] = dp[i - 1][j];

这里可能有录友还疑惑，为什么只考虑 “不用s[i - 1]来匹配” 这种情况， 不考虑 “不用t[j - 1]来匹配” 的情况呢。

这里大家要明确，我们求的是 s 中有多少个 t，而不是 求t中有多少个s，所以只考虑 s中删除元素的情况，即 不用s[i - 1]来匹配 的情况。

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][j]的定义，不要凭感觉初始化。

dp[i][0]表示什么呢？

dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。

那么dp[i][0]一定都是1 因为也就是把以i-1为结尾的s 删除所有元素 出现空字符串的个数就是1。

再来看dp[0][j]，dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。

那么dp[0][j]一定都是0，s如论如何也变成不了t。

最后就要看一个特殊位置了，即：dp[0][0] 应该是多少。

dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。

初始化分析完毕，代码如下：

vector<vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1));
for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
for (int j = 1; j <= t.size(); j++) dp[0][j] = 0; // 其实这行代码可以和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][j]可以根据之前计算出来的数值进行计算。

代码如下：

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];
        }
    }
}
//c++

举例推导dp数组

以s："baegg"，t："bag"为例，推导dp数组状态如下：

Java： 

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
//        dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
        for (int i = 0; i < s.length(); i++) {
            dp[i][0] = 1;
        }
        // dp[0][j]怎么都不可能从空字符串变成t 一定为0
        // dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。
        for (int i = 1; i < s.length() + 1; i++) {
            for(int j = 1; j < t.length() + 1; j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    //考虑i和j相同 加入 注意初始化条件 
                    //不考虑i 后面可能还有一样的字符 所以直接把上次的值传下来就行
                }else{
                    dp[i][j] = dp[i - 1][j];//把当前行元素跳过
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

Carl哥 nb 

583. 两个字符串的删除操作  

题目链接：583. 两个字符串的删除操作 - 力扣（LeetCode）

讲解链接：代码随想录

定义二维数组dp含义 定义dp 以i-1为结尾的字符串word1和以j-1为结尾的字符串word2 想要达到相等 需要删除元素的最少次数dp[i][j]
2 递推公式 当word1遍历当前字符和word2遍历当前字符相同 不需要删除 dp[i][j] = dp[i - 1][j - 1] 当字符不同时 有三种情况 只删word1[i-1] 只删word2[j - 1] 两个都删 word1[i -1]和word2[j - 1] 
dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j - 1] + 1)//当前情况已经省略了两个都删除的情况 因为这种情况被前两者保留 我不太理解 但是也能模糊的理解意思 相当于删了1的第i个字符 保留2的j-1个字符 当前字符为i - 1个 j - 1个 等同于第三种情况 
3 初始化dp 要求删除word1中字符的最少操作次数 那dp[i][0]代表删除最少多少次当前字符长度才能变成空字符串 很明显dp[i][0] = i dp[0][j] = j 同理
4 根据递推公式来看 应该是从前往后 从上到下的顺序
5 试一试

class Solution {
    public int minDistance(String word1, String word2) {
        //定义dp 以i-1为结尾的字符串word1和以j-1为结尾的字符串word2
        //想要达到相等 需要删除元素的最少次数dp[i][j]
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 0; i <= word1.length(); i++){
            dp[i][0] = i;//删除多少个元素i才能变成空字符串j
        }
        for (int i = 0; i <= word2.length(); i++) {
            dp[0][i] = i;//删除多少元素j此案变成空字符串i
        }
        for(int i = 1; i < word1.length() + 1; i++){
            for(int j = 1; j < word2.length() + 1; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    //需要考虑三种情况
                    //1 只删word1 2 只删word2 3 两个都删了
//                    dp[i][j] = Math.min(dp[i - 1][j] + 1,Math.min(dp[i - 1][j],dp[i - 1][j - 1] + 2));
                    //但是两个都删了其实被包含在前两个情况里 可以删去dp[i-1][j-1] + 2
                    dp[i][j] = Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

72. 编辑距离  

题目链接：72. 编辑距离 - 力扣（LeetCode）

讲解链接：代码随想录

1 定义dp数组 word1 word2操作的最少次数dp[i][j]
2 递推公式推导 分为两大类

当前遍历1 2 字符相等则dp[i][j] = dp[i - 1][j - 1]不需要操作就满足条件 当前遍历字符 1  2 不同 分为三种情况 增加一个 减少一个 修改一个 增加和减少实际上是相对的 一致的操作 增加word1一个字符其实就是减少word2的一个字符 操作次数都是1 但是结果一致

以删除操作为准 当删除word1的当前字符i dp[i][j] = dp[i - 1][j] + 1 当删除word2的当前字符j dp[i][j] = dp[i][j - 1] +1 修改一个字符意味着两个字符直接相同 那就是dp[i][j] = dp[i - 1][j - 1] + 1 相同不需要做如何操作 但是这里其实是做了一次修改的操作两个字符i j才相同 所以dp[i][j] = dp[i - 1][j - 1] + 1 （贴上Carl哥的解释 更清晰）操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。

3 初始化（我自己老错）回顾一下dp定义 以下标i - 1为结尾的wprd1字符串和以下标为j - 1为结尾的字符串的编辑距离的最小值dp[i][j](最少操作数)
4 遍历顺序 从递推公式来看 就是从上到下 从左到右
5 试试看

Java：

class Solution {
    public int minDistance(String word1, String word2) {
        if(word1.isEmpty()) return word2.length();
        if(word2.isEmpty()) return word1.length();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i <= word1.length(); i++) {
            //int i = 1
            dp[i][0] = i;
        }
        for (int i = 0; i <= word2.length(); i++) {
            //int i = 1
            dp[0][i] = i;
        }
        for(int i = 1; i < word1.length() + 1; i++){
            for(int j = 1; j < word2.length() + 1; 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, Math.min(dp[i][j - 1] + 1,dp[i - 1][j - 1] + 1));
                    //增加字符和删除字符其实是一样的 相对来说 增加word1的一个字符就是减少word2的一个字符 因为只要求最少的操作次数
                    //所以其实可以视为一个操作 就是删除字符 删除word1 使得word1[i-1]和word2[j]相同 操作次数 + 1
                    //删除word2 使得word[i]和word[j - 1]相同 操作次数 + 1
                    //修改字符意味着把当前字符直接修改成一样的字符 所以dp[i][j]的状态值应该
                    //直接为上次相同的状态值 + 1次操作次数 最后取最小值得出最小次数
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

编辑距离总结篇 

 对于编辑距离来说 我觉得最关键的就是题目对当前字符串的操作是怎么操作 以及在动态规划中这些操作如何实现 用状态转换的想法实现操作 比如删除或者修改 以达到同样字符的效果的操作 实际上就是对1字符串的删除或者2字符串的删除 dp[i][j] = dp[i - 1][j] + 1 或者 dp[i][j]  = dp[i][j - 1] + 1 转换成公式再加上自己思考才能理解清楚 题目想要的是什么 和自己写动态规划方程的有什么区别 能不能达到效果 要把动态规划方程理解清楚 最好的办法就是自己能想得通往回走的状态方程值 直到追溯至dp[0][0] dp[i][0] dp[0][j] 等 

在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！

在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！

在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！

明白动态规划方程的定义 无论是递推公式还是初始化还是遍历方式还是尝试自己推结果 都有一个起码的标准

打卡打卡

标签：四十五天,删除,int,随想录,编辑,word1,word2,字符串,dp
From： https://blog.csdn.net/chengooooooo/article/details/145068096