问题

最小编辑距离 Minimum Edit Distance
关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。
设A、B为两个字符串，狭义的编辑距离定义为把A转换成B需要的最少删除（删除A中一个字符）、插入（在A中插入一个字符）和替换（把A中的某个字符替换成另一个字符）的次数，用ED（A，B）来表示。直观来说，两个串互相转换需要经过的步骤越多，差异越大。
例如 s1 = “12433” 和 s2 = “1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)

性质

计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质:

1.   d(s1,"") = d("",s1) = |s1|
     d("c1","c2") = c1 == c2 ? 0 : 1;
2.   d(s1+c1,s2+c2) = min(  d(s1,s2)+ c1==c2 ? 0 : 1 ,
                            1 + d(s1+c1,s2),
                            1 + d(s1,s2+c2)  );

第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法，于是对c1,c2可能的操作只有：

1.  把c1变成c2
2.  s1+c1后删除c1              d = (1 + d(s1, s2 + c2))
3.  s1+c1后插入c2              d = (1 + d(s1 + c1, s2))

对于2和3的操作可以等价于:
_2.   s2+c2后添加c1        d = (1 + d(s1, s2 + c2))
_3.   s2+c2后删除c2        d = (1 + d(s1 + c1, s2))

因此可以得到计算编辑距离的性质2。

复杂度分析

从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为 n )
可以看到，该问题的复杂度为指数级别 3 的 n 次方，对于较长的串，时间上是无法让人忍受的。
分析: 在上面的结构中，我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

动态规划求解

首先为了避免重复计算子问题，添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s1[i] = s2[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到

M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;

根据性质2得到

M[ i, j ]   = min(  m[i-1,j-1] + E[ i, j ] ,
                    1 + m[i, j-1] ,
                    1 + m[i-1, j]  );

复杂度
从新的计算式看出，计算过程为

      i=1 -> |s1|
             j=1 -> |s2|
                    M[i][j] = ……

因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)

改进

当s[i]和s[j]相等时，代价为0，必然为最小值，所以首先判断两字符是否相等，若相等则直接判定M[i][j]=M[i-1][j-1]，判断下个。这样可以省很多计算。

工具宏：直接用一个宏来完成“求取三者最小值”的功能。不同于递归，宏定义消耗很小，完全可以放心使用。

#ifndef _MIN(xyz)
#define _MIN(xyz) ((x<y)?((x<z)?x:z):((y<z)?y:z))
#endif // _MIN(xyz)