动态规划求解
首先为了避免重复计算子问题，添加两个辅助数组。
一.保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串
s1(0->i) 与 s2(0->j) 的编辑距离
二.保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ]
= s[i] = s[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 ] ,
m[i, j-1] , m[i-1, j]);
复杂度
从新的计算式看出，计算过程为
i=1 -> |s1|
j=1 -> |s2|
M[i][j] = ……
因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)