一、实践题目
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：
(1)删除一个字符；
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。
对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。 输入格式: 第一行是字符串A，文件的第二行是字符串B。 提示：字符串长度不超过2000个字符。 输出格式: 输出编辑距离d(A,B) 输入样例: 在这里给出一组输入。例如： fxpimu xwrs 输出样例: 在这里给出相应的输出。例如： 5
二、问题描述
题目大意是：给出两个字符串 a、b，可以通过增删改三个操作将a变成b，需要进行几次操作。
三、算法描述
这道题类似于求最长公共子序列，但是还是更高级一点的。我用了res [2002][2002]来存储结果，res[i][j]表示a的子串(下标从0到i）转化为b的子串（下标从0到j）需要的操作次数，因此本题结果是res[strlen(a)][strlen(b)]。
那么问题就转化为求出res数组。
本题的res数组:
1、初始化：当strlen(a)=0,res[0][j]=j;同理可得res[i][0]=i;
2、当a[i-1]=b[j-1],则res[i][j]=res[i-1][j-1]，即等于左上角的元素;
3、当a[i-1]!=b[j-1]，有以下三种情况：
（1）若进行删除操作：操作数加1，res[i][j]=res[i-1][j]+1;
（2）若进行增加操作：操作数加1，res[i][j]=res[i][j-1]+1;
（3）若进行替换操作：操作数加1，res[i][j]=res[i-1][j-1]+1;
res[i][j]等于上面三种情况res[i][j]里的最小值
通过以上分析，我们可以发现填表规则是从上到下从左往右填一个大小为strlen(a)*strlen(b)的表格，两层for循环对res数组操作：匹配时取左上的值；
失配时取 左上+1，左边+1，右边+1 三个数中的最小值，更新res[i]][j];
最后递推到右下角dp[la][lb]为所求答案
四、算法时间及空间复杂度分析
采用dp思想，两层for循环处理res数组，故时间复杂度为O（n^2）
五、心得体会
dp问题最重要的还是要找到问题的最优解子结构，然后建立递推关系，确定好填表的顺序。
多打题，才能提高、加深对算法的理解。