问题描述：
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。
个人对问题的理解：设两个字符串s[0:i],t[0:j]，用最少的操作数（三种：增删换，三种各花销一次操作）将s变成t（或者t变成s，同等），先解决三种特殊情况
1）s为空，t不为空；
2）t为空，s不为空；
3）s与t相等；
对于第一第二种情况，即在i等于0时，也就是说s为空，增加j个字符，使得s转化为t，在j等于0时，也就是说t为空，就是减少 i个字符，使得s转化为t。
对于第三种情况，显然为d(A,B)=0。
算法描述：
1）现在只剩下普通（一般）情况，运用动态规划求出递归方程，将原问题分解为若干个子问题进行求最优解，后得出原问题的最优解，采用“填表的方法”，设计步骤：对每个子问题只求解一次，将其结果保存在一张表（构造一个行数为n+1 列数为 m+1 的
版权声明：本文为bensonrachel原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。