有经验的程序员每次提交代码时都要开启比对工具，任意一个插入、删除、修改字符都会被高亮标记出来，这里就需要用到编辑距离算法。俄罗斯科学家弗拉基米尔·莱文斯坦（Vladimir Levenshtein）于1965年提出了莱文斯坦距离（Levenshtein distance）算法，用于度量两个字符串通过插入、删除或替换操作转换为彼此所需的最少编辑次数。该算法应用非常广泛除了文本差异对比外，还经常用于拼写校正、DNA序列比对、及OCR纠错等等。
在标准的 Levenshtein 距离中，插入、删除、替换的代价都是 1。分析经典的source = "kitten", target="sitting" 例子的 DP 矩阵， 如下
观察后，我猜测：任意一个矩阵元素和相邻的左方、上方、左上方、右方、下方、右下方的距离差绝对值小于等于1。
不包括右上方、左下方，距离差绝对值可能达到2，上面的例子很容易找到。下面给出证明。
证明：
令 $D(i, j)$ 表示字符串 $A$ 的前 $i$ 个字符与字符串 $B$ 的前 $j$个字符之间的标准 Levenshtein 距离。由于矩阵中相邻元素的对称性（例如："A在 B 的左边" 等价于 "B在A的右边"），我们只需要证明左方、上方、左上方这三个方向的绝对差值小于等于1即可。
1. 水平方向（左方 / 右方）
我们要证明：$|D(i, j) - D(i, j-1)| \le 1$
根据编辑距离的定义（三角不等式原理）：
- $D(i, j)$ 是将 $A[1..i]$ 转换为 $B[1..j]$ 的最少操作次数。
- $D(i, j-1)$ 是将 $A[1..i]$ 转换为 $B[1..j-1]$ 的最少操作次数。
从 $B[1..j-1]$ 到 $B[1..j]$ 只需要增加一个字符 $B[j]$（代价为1）。因此：
$$D(i, j) \le D(i, j-1) + 1 \implies D(i, j) - D(i, j-1) \le 1$$
同理，从 $B[1..j]$ 到 $B[1..j-1]$ 只需要删除一个字符 $B[j]$（代价为1）。因此：
$$D(i, j-1) \le D(i, j) + 1 \implies D(i, j) - D(i, j-1) \ge -1$$
结合两式，可得 $-1 \le D(i, j) - D(i, j-1) \le 1$，即：
$$|D(i, j) - D(i, j-1)| \le 1$$
2. 垂直方向（上方 / 下方）
我们要证明：$|D(i, j) - D(i-1, j)| \le 1$
逻辑与水平方向完全相同。$A[1..i]$ 与 $A[1..i-1]$ 之间只相差一个字符$A[i]$ 的插入或删除操作（代价为 1）。
根据三角不等式，改变其中一个字符串的一个字符，编辑距离的变化量绝对值最大为1。因此：
$$|D(i, j) - D(i-1, j)| \le 1$$
3. 主对角线方向（左上方 / 右下方）
我们要证明：$|D(i, j) - D(i-1, j-1)| \le 1$
根据 Levenshtein 距离的状态转移方程：
$$D(i, j) = \min \begin{cases} D(i-1, j) + 1 \\ D(i, j-1) + 1 \\ D(i-1, j-1) + \text{cost} \end{cases}$$
其中 $\text{cost} \in \{0, 1\}$。
- 证明上限： 由于 $D(i, j)$
是三者取极小值，它必然小于或等于第三项：
$$D(i, j) \le D(i-1, j-1) + \text{cost} \le D(i-1, j-1) + 1$$
由此可得：$D(i, j) - D(i-1, j-1) \le 1$。
- 证明下限：
我们分别看状态转移方程中的三项与 $D(i-1, j-1)$ 的大小关系：
1. 第一项：由水平方向结论可知 $D(i-1, j) \ge D(i-1, j-1) - 1$，因此
$D(i-1, j) + 1 \ge D(i-1, j-1)$。
2. 第二项：由垂直方向结论可知 $D(i, j-1) \ge D(i-1, j-1) - 1$，因此
$D(i, j-1) + 1 \ge D(i-1, j-1)$。
3. 第三项：因为 $\text{cost} \ge 0$，所以
$D(i-1, j-1) + \text{cost} \ge D(i-1, j-1)$。
既然这三项全部都大于或等于$D(i-1, j-1)$，那么它们的最小值也必然大于或等于 $D(i-1, j-1)$：
$$D(i, j) \ge D(i-1, j-1) \implies D(i, j) - D(i-1, j-1) \ge 0 \ge -1$$
结合上限与下限，实际上我们证明了一个更强的结论：
$$0 \le D(i, j) - D(i-1, j-1) \le 1$$
其绝对值自然满足：
$$|D(i, j) - D(i-1, j-1)| \le 1$$
