编辑距离问题 动态规划（编辑距离计算相似度）
预计阅读时间：8 分钟
前几天在网上看到一份鹅场的面试题，算法部分大半是动态规划，最后一题就是写一个计算编辑距离的函数，今天就专门写一篇文章来探讨一下这个经典问题。
我个人很喜欢编辑距离这个问题，因为它看起来十分困难，解法却出奇得简单漂亮，而且它是少有的比较实用的算法（是的，我承认很多算法问题都不太实用）。下面先来看下题目：
为什么说这个问题难呢，因为显而易见，它就是难，让人手足无措，望而生畏。
为什么说它实用呢，因为前几天我就在日常生活中用到了这个算法。之前有一篇公众号文章由于疏忽，写错位了一段内容，我决定修改这部分内容让逻辑通顺。但是公众号文章最多只能修改 20 个字，且只支持增、删、替换操作（跟编辑距离问题一模一样），于是我就用算法求出了一个最优方案，只用了 16 步就完成了修改。
再比如高大上一点的应用，DNA 序列是由 A,G,C,T 组成的序列，可以类比成字符串。编辑距离可以衡量两个 DNA 序列的相似度，编辑距离越小，说明这两段 DNA 越相似，说不定这俩 DNA 的主人是远古近亲啥的。
下面言归正传，详细讲解一下编辑距离该怎么算，相信本文会让你有收获。
一、思路
编辑距离问题就是给我们两个字符串s1和s2，只能用三种操作，让我们把s1变成s2，求最少的操作数。需要明确的是，不管是把s1变成s2还是反过来，结果都是一样的，所以后文就以s1变成s2举例。
前文最长公共子序列 说过，解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。
设两个字符串分别为 "rad" 和 "apple"，为了把s1变成s2，算法会这样进行：
请记住这个 GIF 过程，这样就能算出编辑距离。关键在于如何做出正确的操作，稍后会讲。
根据上面的 GIF，可以发现操作不只有三个，其实还有第四个操作，就是什么都不要做（skip）。比如这个情况：
因为这两个字符本来就相同，为了使编辑距离最小，显然不应该对它们有任何操作，直接往前移动i,j即可。
还有一个很容易处理的情况，就是j走完s2时，如果i还没走完s1，那么只能用删除操作把s1缩短为s2。比如这个情况：
类似的，如果i走完s1时j还没走完了s2，那就只能用插入操作把s2剩下的字符全部插入s1。等会会看到，这两种情况就是算法的base case。
下面详解一下如何将这个思路转化成代码，坐稳，准备发车了。
二、代码详解
先梳理一下之前的思路：
base case 是i走完s1或j走完s2，可以直接返回另一个字符串剩下的长度。
对于每对儿字符s1[i]和s2[j]，可以有四种操作：
ifs1[i] == s2[j]:
啥都别做（skip）
i, j 同时向前移动
else:
三选一：
插入（insert）
删除（delete）
替换（replace）
有这个框架，问题就已经解决了。读者也许会问，这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁。这里需要递归技巧，理解需要点技巧，先看下代码：
下面来详细解释一下这段递归代码，base case 应该不用解释了，主要解释一下递归部分。
都说递归代码的可解释性很好，这是有道理的，只要理解函数的定义，就能很清楚地理解算法的逻辑。我们这里 dp。不难，但是可解释性大大降低，读者可以自己尝试优化一下。
你可能还会问，这里只求出了最小的编辑距离，那具体的操作是什么？之前举的修改公众号文章的例子，只有一个最小编辑距离肯定不够，还得知道具体怎么修改才行。
这个其实很简单，代码稍加修改，给 dp 数组增加额外的信息即可：
// int[][] dp;
Node[][] dp;
classNode{
intval;
intchoice;
// 0 代表啥都不做
// 1 代表插入
// 2 代表删除
// 3 代表替换
}
val属性就是之前的 dp 数组的数值，choice属性代表操作。在做最优选择时，顺便把操作记录下来，然后就从结果反推具体操作。
我们的最终结果不是dp[m][n]吗，这里的val存着最小编辑距离，choice存着最后一个操作，比如说是插入操作，那么就可以左移一格：
重复此过程，可以一步步回到起点dp[0][0]，形成一条路径，按这条路径上的操作编辑对应索引的字符，就是最佳方案：
这就是编辑距离算法的全部内容，希望本文对你有帮助。
●编号1005，输入编号直达本文