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

**动态规划——583.两个字符串的删除操作**

在 LeetCode 上，存在一个问题：给定两个字符串 `s1` 和 `s2`，要求你找出将 `s1` 转换为 `s2` 的最少删除次数。这个问题可以用动态规划来解决。

**动态规划——72. 编辑距离**

另一个相关的问题是编辑距离，也就是给定两个字符串 `s1` 和 `s2`，要求你找出将 `s1` 转换为 `s2` 的最少编辑操作次数。这个问题也可以用动态规划来解决。

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

### 动态规划我们先来分析一下这个问题。给定两个字符串 `s1` 和 `s2`，要求你找出将 `s1` 转换为 `s2` 的最少删除次数。我们可以用一个二维数组 `dp` 来存储每个子串的最少删除次数。

cppclass Solution {
public:
 int minDistance(string word1, string word2) {
 int m = word1.size();
 int n = word2.size();
 // dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最少删除次数 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]) +1;
 }
 }
 }
 return dp[m][n];
 }
};

### 解释我们首先初始化 `dp` 的第一行和第一列。然后，我们从左下角开始遍历 `dp`，对于每个位置 `(i, j)`，如果 `word1[i -1] == word2[j -1]`，则 `dp[i][j] = dp[i -1][j -1]`；否则，`dp[i][j] = min(dp[i -1][j], dp[i][j -1]) +1`。

### 时间复杂度时间复杂度为 O(m * n)，其中 m 和 n 是 `word1` 和 `word2` 的长度。

### 空间复杂度空间复杂度为 O(m * n)。

---

**72. 编辑距离**

另一个相关的问题是编辑距离，也就是给定两个字符串 `s1` 和 `s2`，要求你找出将 `s1` 转换为 `s2` 的最少编辑操作次数。这个问题也可以用动态规划来解决。

### 动态规划我们先来分析一下这个问题。给定两个字符串 `s1` 和 `s2`，要求你找出将 `s1` 转换为 `s2` 的最少编辑操作次数。我们可以用一个二维数组 `dp` 来存储每个子串的最少编辑操作次数。

cppclass Solution {
public:
 int minDistance(string word1, string word2) {
 int m = word1.size();
 int n = word2.size();
 // dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最少编辑次数 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]) +1;
 }
 }
 }
 return dp[m][n];
 }
};

### 解释我们首先初始化 `dp` 的第一行和第一列。然后，我们从左下角开始遍历 `dp`，对于每个位置 `(i, j)`，如果 `word1[i -1] == word2[j -1]`，则 `dp[i][j] = dp[i -1][j -1]`；否则，`dp[i][j] = min(dp[i -1][j], dp[i][j -1]) +1`。

### 时间复杂度时间复杂度为 O(m * n)，其中 m 和 n 是 `word1` 和 `word2` 的长度。

### 空间复杂度空间复杂度为 O(m * n)。

---

以上是关于 LeetCode | C++ 动态规划——583.两个字符串的删除操作、72. 编辑距离 的内容。