我个人很喜欢编辑距离这个问题，因为它看起来十分困难，解法却出奇得简单漂亮，而且它是少有的比较实用的算法（我承认很多算法问题都不太实用）。
力扣第 72 题「编辑距离」就是这个问题，先看下题目：
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入： word1 = “horse”, word2 = “ros” 输出： 3 解释： horse → rorse (将 ‘h’ 替换为 ‘r’) rorse → rose (删除 ‘r’) rose → ros (删除 ‘e’)
示例 2：
输入： word1 = “intention”, word2 = “execution” 输出： 5 解释： intention → inention (删除 ‘t’) inention → enention (将 ‘i’ 替换为 ‘e’) enention → exention (将 ‘n’ 替换为 ‘x’) exention → exection (将 ‘n’ 替换为 ‘c’) exection → execution (插入 ‘u’)
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
为什么说这个问题难呢，因为显而易见，它就是难，让人手足无措，望而生畏。
为什么说它实用呢，因为前几天我就在日常生活中用到了这个算法。之前有一篇公众号文章由于疏忽，写错位了一段内容，我决定修改这部分内容让逻辑通顺。但是公众号文章最多只能修改 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。
下面详解一下如何将思路转换成代码