此题乍看之下有点摸不着头脑，但其实属一道非常经典的题目。
有兴趣的童鞋可以看看这个 Stanford 的 Minimum Edit Distance
而这道小题，只是上述大论题中最简单的情况：连 Replace 操作也仅算一步，各操作都被一视同仁。
我们从实际例子开始分析，看以下几组单词：
graffe
graf
^^
insert(2)
graffe
graft
^^
replace + insert
graffe
grail
^^^
replace(2) + insert
graffe
giraffe
^
delete
上述就是咱们人脑推断出来的过程，看起来比较直接，一眼就分辨出来了。但如何用代码来表述这个过程，却是一个难题。假设第一个单词为 word1, 长度为 n; 第二个单词为 word2, 长度为 m.
直接去比较 n 与 m 长度的字符串显然无从下手，那么我们简化问题，首先考虑 0 长度，若 m == 0, 则显然应该返回 n， 反之亦然。
if (m == 0) return n;
if (n == 0) return m;假设 word1 的当前 pos 为 i, word2 的当前 pos 为 j，上述情况就是 i=n 以及 j=m 的时候。如果我们用 distance(i, j) 来表示问题的解，那么最终要求的，便是 distance(n, m).
然后回到上述实例，前三组都有一个特点，就是前缀相同：
gra
gra
请问，相同的前缀 gra 对咱们的结果有影响吗？如果都是 g 呢？如果都是 gr 呢？是的，都一样，最终的 distance 是一样的， 故有:
if (word1[i] == word2[j]) distance(i, j) = distance(i-1, j-1); // [定理1]
那就要问了，若 word1[i] != word2[j] 呢？如第三组：
|graf == |f
|grai |i
^
根据[定理1]
显然，简化后仅需要一个 replace 操作，故应为 gra 的情况下 +1，即
else A[i][j] = distance(i-1, j-1) + 1;
^
// 这里加的数取决于 replace 操作需要消耗的 distance
难道规律已然被我们找到？但为何仅仅用到了 replace 操作呢？用 insert 和 delete 不行吗？再看第一组：
|graffe == |fe == distance(i, j)
|graf |
^
根据[定理1]
简化后的结果，我们很容易看出 word2 需要 insert 两次。如果将 i 倒退一步， 可以发现：
distance(i, j) == distance(i-1, j) + |e == distance(i-1, j) + 1; // [定理2]
|
^
// 这里加的数取决于 insert 操作需要消耗的 distance
同理咱们分析第四组：
|graffe == |g == distance(i, j)
|giraffe |gi
^
根据[定理1]
简化后的结果，我们也能较容易看出 word2 需要 delete 一次。但如果将 j 倒退一步，可以发现：
distance(i, j) == distance(i, j-1) + | == distance(i, j-1) + 1; // [定理3]
|i
^
// 这里加的数取决于 delete 操作需要消耗的 distance
到此为止，我们发现存在三种方式，将 distance 消灭为0，可以总结如下：
__ true : distance(i-1, j-1) // [定理1]
|_ word1[i] ?= word2[j] |
distance(i, j) == | |__ false : distance(i-1, j-1) + op(replace)
|_ distance(i-1, j) + op(insert) // [定理2]
|_ distance(i, j-1) + op(delete) // [定理3]
我们要求的是最小的 distance ，那么根据上述公式，我们所求的不过是这三种情况的最小值。在这道题里:
op(replace) == op(insert) == op(delete) == 1
最后，我们发现想要表述 distance(i, j)，需依赖一个 n*m 的矩阵，将每一次子串比较的结果保存下来。
这种通过"矩阵"的方式，来积累每一次子问题结果的手段，是非常非常明显的** DP (动态规划问题) ** 。 想一想 [29. Unique Paths](../29. Unique Paths)，再想想杨辉三角，就会发现其本质完全一致。
由于 DP 问题，十分依赖上一次的结果，而对于 nm 的解空间矩阵来说，首行与首列，是无法通过 DP 手段计算出的，若仍想要依赖 DP。我们需要在外面手工包一层。即让整个解空间矩阵(nm)都有上一次的结果可依。
那么就成了一个 (n+1) * (m+1) 的矩阵了。
对于首行，即 i 不变， j 递增，即：
|
|gggg ...
显然属于[定理3]的范畴，可知第一行为：{0, 1, 2, 3 ...}
同理，对于首列，即 j 不变， i 递增，即：
|gggg ...
|
显然属于[定理2]的范畴，可知第一列为：{0, 1, 2, 3 ...}
最终矩阵的外壳，看起来就是：
_ _
|0 1 2 3 4 5 ... |
|1
|2
|3
|4
|5
|.
|.
|_ _ |
而我们需要做的，便是填充这个矩阵，问题的最终解是该矩阵右下角的值：A[n][m].