> For the complete documentation index, see [llms.txt](https://hswsp.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hswsp.gitbook.io/algorithm/dynamic-programming/jing-dong-tai-gui-hua-bian-ji-ju-li.md).

# 经动态规划：编辑距离

下面先来看下题目：

![](/files/-Me9ESBpeDx2Vfe9nI_u)

为什么说这个问题难呢，因为显而易见，它就是难，让人手足无措，望而生畏。

为什么说它实用呢，因为前几天我就在日常生活中用到了这个算法。之前有一篇公众号文章由于疏忽，写错位了一段内容，我决定修改这部分内容让逻辑通顺。但是公众号文章最多只能修改 20 个字，且只支持增、删、替换操作（跟编辑距离问题一模一样），于是我就用算法求出了一个最优方案，只用了 16 步就完成了修改。

再比如高大上一点的应用，DNA 序列是由 A,G,C,T 组成的序列，可以类比成字符串。**编辑距离可以衡量两个 DNA 序列的相似度，编辑距离越小，说明这两段 DNA 越相似**，说不定这俩 DNA 的主人是远古近亲啥的。

下面言归正传，详细讲解一下编辑距离该怎么算，相信本文会让你有收获。

## 一、思路

编辑距离问题就是给我们两个字符串`s1`和`s2`，只能用三种操作，让我们把`s1`变成`s2`，求最少的操作数。需要明确的是，不管是把`s1`变成`s2`还是反过来，结果都是一样的，所以后文就以`s1`变成`s2`举例。

前文 [最长公共子序列](http://mp.weixin.qq.com/s?__biz=MzU0MDg5OTYyOQ==\&mid=2247484418\&idx=1\&sn=98b1aa8c105467efab24e677fb17ff1a\&chksm=fb336440cc44ed564f10ace689aa8e88e6d4a684cda2d2c07e81fad45cb4a70d1c27f4309ec4\&scene=21#wechat_redirect) 说过，**解决两个字符串的动态规划问题，一般都是用两个指针`i,j`分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模**。

设两个字符串分别为 "rad" 和 "apple"，为了把`s1`变成`s2`，算法会这样进行：

![](/files/-Me9FfePrLdypSimgzWB)

![](/files/-Me9FqsNBlofCHxOwAh4)

请记住这个 GIF 过程，这样就能算出编辑距离。关键在于如何做出正确的操作，稍后会讲。

根据上面的 GIF，可以发现操作不只有三个，其实还有第四个操作，就是什么都不要做（skip）。比如这个情况：

![](/files/-Me9FwN_iDpnlGaPVZbB)

因为这两个字符本来就相同，为了使编辑距离最小，显然不应该对它们有任何操作，直接往前移动`i,j`即可。

还有一个很容易处理的情况，就是`j`走完`s2`时，如果`i`还没走完`s1`，那么只能用删除操作把`s1`缩短为`s2`。比如这个情况：

![](/files/-Me9GNWuSipIlHmdHNOn)

类似的，如果`i`走完`s1`时`j`还没走完了`s2`，那就只能用插入操作把`s2`剩下的字符全部插入`s1`。等会会看到，这两种情况就是算法的 **base case**。

下面详解一下如何将这个思路转化成代码，坐稳，准备发车了。

## 二、代码详解

先梳理一下之前的思路：

base case 是`i`走完`s1`或`j`走完`s2`，可以直接返回另一个字符串剩下的长度。

对于每对儿字符`s1[i]`和`s2[j]`，可以有四种操作：

```cpp
if s1[i] == s2[j]:
    啥都别做（skip）
    i, j 同时向前移动
else:
    三选一：
        插入（insert）
        删除（delete）
        替换（replace）
```

有这个框架，问题就已经解决了。读者也许会问，**这个「三选一」到底该怎么选择呢**？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁。**这里需要递归技巧**，理解需要点技巧，先看下代码：

![](/files/-Me9GfxtUcW6N1T41zII)

下面来详细解释一下这段递归代码，base case 应该不用解释了，主要解释一下递归部分。

都说递归代码的可解释性很好，这是有道理的，只要理解函数的定义，就能很清楚地理解算法的逻辑。我们这里 dp(i, j) 函数的定义是这样的：

```python
def dp(i, j) -> int
# 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
```

**记住这个定义**之后，先来看这段代码：

```python
if s1[i] == s2[j]:
    return dp(i - 1, j - 1)  # 啥都不做
# 解释：
# 本来就相等，不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小编辑距离等于
# s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
# 也就是说 dp(i, j) 等于 dp(i-1, j-1)
```

如果`s1[i]！=s2[j]`，就要对三个操作递归了，稍微需要点思考：

```python
dp(i, j - 1) + 1,    # 插入
# 解释：
# 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
# 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
# 别忘了操作数加一
```

![](/files/-Me9JS1bK5AGRLs2fG_v)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hswsp.gitbook.io/algorithm/dynamic-programming/jing-dong-tai-gui-hua-bian-ji-ju-li.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.