本文主要是介绍Day48- 动态规划part16，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、两个字符串的删除操作
题目一：583. 两个字符串的删除操作
583. 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
这个问题实际上是求两个字符串的最长公共子序列（LCS）的长度的变种。一旦找到了最长公共子序列的长度，通过删除两个字符串中不在LCS中的所有字符来使它们相同。因此，所需的最小删除步数就是两个字符串的长度之和减去两倍的LCS长度。
初始化一个二维数组
dp，其中dp[i][j]表示word1的前i个字符和word2的前j个字符的最长公共子序列的长度。数组的大小为(len(word1) + 1) x (len(word2) + 1)，加 1 是因为从空字符串开始考虑。遍历
word1和word2，更新dp数组。如果word1[i-1] == word2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。最长公共子序列的长度为
dp[len(word1)][len(word2)]。所需的最小删除步数为len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)]。
class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (word1[i-1] == word2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}}return m + n - 2 * dp[m][n];}
};二、编辑距离
题目一：72. 编辑距离
72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
计算将一个字符串转换为另一个字符串的最少操作数，这些操作包括插入、删除和替换字符。
定义一个二维数组
dp，其中dp[i][j]表示从word1的前i个字符转换到word2的前j个字符所需的最少操作数。以下是解决这个问题的步骤：
初始化一个二维数组
dp的大小为(len(word1) + 1) x (len(word2) + 1)。dp[0][j]表示从空字符串转换到word2的前j个字符所需的最少操作数，即j（全部插入操作）。类似地，dp[i][0]表示从word1的前i个字符转换到空字符串所需的最少操作数，即i（全部删除操作）。遍历
word1和word2，更新dp数组。对于每对(i, j)，如果word1[i-1] == word2[j-1]，则dp[i][j] = dp[i-1][j-1]；否则，dp[i][j]是以下三种操作的最小值加一：
- 插入：
dp[i][j-1] + 1- 删除：
dp[i-1][j] + 1- 替换：
dp[i-1][j-1] + 1
dp[len(word1)][len(word2)]就是将word1转换为word2所需的最少操作数。
class Solution {
public:int minDistance(string word1, string word2) {int m = word1.length(), n = word2.length();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; 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], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;}}}return dp[m][n];}
};这篇关于Day48- 动态规划part16的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
