代码随想录二刷day56 | 动态规划之 583. 两个字符串的删除操作 72. 编辑距离

**代码随想录二刷 Day56 | 动态规划之583.两个字符串的删除操作72. 编辑距离**

## 前言在前面的日志中，我们已经学习了动态规划的基本概念和应用。今天，我们将继续深入探讨动态规划的另一个经典问题——583.两个字符串的删除操作，也就是我们熟悉的编辑距离问题。

## 编辑距离问题描述给定两个字符串 `s1` 和 `s2`，要求计算出将 `s1` 转换成 `s2` 的最少操作次数。这些操作包括：

* **插入**: 在 `s1` 中插入一个字符。
* **删除**: 从 `s1` 中删除一个字符。
* **替换**: 将 `s1` 中的一个字符替换为另一个字符。

## 动态规划解决方案我们可以使用动态规划来解决这个问题。动态规划的基本思想是：对于每个子串 `s1[i..j]` 和 `s2[k..m]`，我们计算出从 `s1[i..j]` 转换成 `s2[k..m]` 的最少操作次数。

### 状态定义我们定义一个二维数组 `dp`，其中 `dp[i][k]` 表示将 `s1[0..i-1]` 转换成 `s2[0..k-1]` 的最少操作次数。

### 递归关系递归关系如下：

* 如果 `s1[i-1] == s2[k-1]`，则 `dp[i][k] = dp[i-1][k-1]`。
* 否则，如果 `i ==0` 或 `k ==0`，则 `dp[i][k] = i + k`（因为需要插入或删除所有字符）。
* 否则，`dp[i][k] = min(dp[i-1][k] +1, dp[i][k-1] +1, dp[i-1][k-1] +1)`。

### 初始化我们初始化 `dp[0][0] =0`，因为将空字符串转换成空字符串的最少操作次数是0。

##代码实现

def minDistance(word1: str, word2: str) -> int:
 m, n = len(word1), len(word2)
 # 初始化动态规划数组 dp = [[0] * (n +1) for _ in range(m +1)]
 # 填充动态规划数组 for i in range(1, m +1):
 for j in range(1, n +1):
 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, dp[i][j -1] +1, dp[i -1][j -1] +1)
 # 返回最少操作次数 return dp[m][n]

print(minDistance("horse", "ros")) # Output:3print(minDistance("", "")) # Output:0print(minDistance("a", "b")) # Output:1print(minDistance("intention", "execution")) # Output:5