1、实践题目 ：7-3 编辑距离问题

2、问题描述：设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。

3、算法描述：

首先分析将A变成B的三个途径：插入，删除，和修改。然后可以开一个二维数组d[i][j]来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求

具体算法：

    dp[i][j]来自于三种状态:

    1、删除，dp[i-1][j]+1;

    2、插入，dp[i][j-1]+1;

    3、替换，if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1],else dp[i][j]=dp[i-1][j-1]+1;

首先给定第一行和第一列，然后，每个值d[i][j]这样计算：

if(s1[j-1] == s2[i-1])    {c[i][j] = c[i-1][j-1];}

else   { c[i][j] = minval(c[i][j-1]+1,c[i-1][j]+1,c[i-1][j-1]+1);}

最后一行，最后一列的那个值就是最小编辑距离

4、算法时间复杂度和空间复杂度分析：

填表时遍历二维数组，所以时间复杂度为O(s1.length()*s2.length())

开了一个二维数组c存最小编辑距离，空间复杂度为O(s1.length() * s2.length())

5、心得体会：  

 在实验室结对编程的时候，我们做到第三题的时候仅有半个多小时了，当时没有太多的时间想到动态规划，一开始想到的是求出最长公共子序列，然后用较长的字符串长度减去最长公共子序列长度就可以得到答案了，但是提交过后发现只有部分答案正确。仔细思考过后发现确实有BUG，如果最长公共子序列不是连续的，那么就会造成有错误：反例（"abd"和"acb"）。下课后和老师讨论了之后发现原来这是一题很典型的动态规划问题。总共有三种改变字符的方法，每改变一个字符，就可以减小字符串s1或s2的长度，最终递归到长度为0就是初始情况：1、目标字符串长度为0，则改变m次（待改字符长度） 2、待改字符长度为0，则改变n次（目标字符长度）。然后根据这个思想开一个二维数组很快就写出了解决办法。最后感慨，动态规划虽然比较难想到，但是如果真的想明白了，会把题目难度降低不少。结对编程的相互讨论加快了我们纠错的时间，不会一直在一个地方卡着，大大节省了编程时间，提高了编程体验。