LeetCode | C++ 动态规划——583. 两个字符串的删除操作、72. 编辑距离-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode | C++ 动态规划——583. 两个字符串的删除操作、72. 编辑距离。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

583题目链接
做法一： 本题和1143.最长公共子序列基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

做法二： 本题和115.不同的子序列相比，其实就是两个字符串都可以删除了

dp[i] [j] 数组含义

以i - 1为结尾的字符串word1，和以j - 1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

递推公式

（1）word1[i - 1] 与 word[j - 1] 相等时，

dp[i] [j] = dp[i - 1] [j - 1]

（2）word1[i - 1] 与 word[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

最后取三者最小值：dp[i] [j] = min(dp[i - 1] [j] + 1, dp[i] [j - 1] + 1, dp[i - 1] [j - 1] + 2)

dp数组初始化

由递推公式得 dp[0] [j] 和 dp[i] [0] 都需要初始化,根据dp 数组定义得

dp[0] [j] = j

dp[i] [0] = i

遍历顺序

从左往右，从上到下

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for (int i = 0; i <= word1.size(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.size(); j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

72. 编辑距离

72题目链接
dp[i] [j] 数组含义

表示以下标i - 1为结尾的字符串word1，和以下标j - 1为结尾的字符串word2，最近编辑距离为dp[i] [j]。

递推公式

（1）如果word1[i - 1] 与 word2[j - 1] 相同：

dp[i] [j] = dp[i - 1] [j - 1]

（2）如果word1[i - 1] 与 word2[j - 1] 相同：又分为 3 种增删改

删：dp[i] [j] = dp[i - 1] [j] + 1;

改：dp[i] [j] = dp[i - 1] [j - 1] + 1;

增：相当于 word2 删除元素，即为以下标i - 1为结尾的 word1 与 j - 2 为结尾的最近编辑距离 + 一个操作

dp[i] [j] = dp[i] [j - 1] + 1;

最后取三者之中最小的， dp[i] [j] = min(dp[i - 1] [j] + 1, min(dp[i - 1] [j - 1] + 1, dp[i] [j - 1] + 1))

dp数组初始化

由递推公式得，dp[0] [j] 和 dp[i] [0] 需要初始化

dp[0] [j] = j

dp[i] [0] = i

遍历顺序

根据递推公式得，从左到右，从上到下文章来源地址https://www.toymoban.com/news/detail-587004.html

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for (int i = 0; i <= word1.size(); i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= word2.size(); j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};