动态规划—最短编辑问题—非常详细分析以及代码

*问题描述：设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。 * 这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； * (3)将一个字符改为另一个字符。将字符串A变换为字符串B 所用的最少 * 字符操作数称为字符串A到B 的编辑距离，记为 d(A,B)。试设计一个有效 * 算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。 * 例如： * 输入第一个字符串： * shao * 输入第二个字符串： * shaod * 最短编辑距离 * 1 (2)本题思路分析 * 定义两个字符串s1 ,s2 * 比较两字符串的某两个相同位置时：(例如s1[i] s2[j] 这时i=j)有三种办法 * 1.把字符ch1变成ch2， 使得s1与s2字符串在该处相同 * 2.删除s1当中的该字符ch1，使得s1与s2字符串在该处相同 * 3.插入某个字符ch2，使得s1与s2字符串在该处相同 运行结果： * 请输入字符串1 * shao * 请输入字符串2 * sha1 * d[1][1]= 0 d[1][2]= 1 d[1][3]= 2 d[1][4]= 3 * * d[2][1]= 1 d[2][2]= 0 d[2][3]= 1 d[2][4]= 2 * * d[3][1]= 2 d[3][2]= 1 d[3][3]= 0 d[3][4]= 1 * * d[4][1]= 3 d[4][2]= 2 d[4][3]= 1 d[4][4]= 1 * * 最短编辑距离为： 1 * 请按任意键继续. . .

/******************************************************************************
                         动态规划--最短编辑问题                                                        
*******************************************************************************/ 


/* 
*问题描述：设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。
*          这里所说的字符操作包括 （1）删除一个字符； （2）插入一个字符； 
*          （3）将一个字符改为另一个字符。将字符串A变换为字符串B 所用的最少
*          字符操作数称为字符串A到B 的编辑距离，记为 d（AB）。试设计一个有效
*          算法，对任给的2 个字符串A和B，计算出它们的编辑距离d（AB）。
*          例如：
*          输入第一个字符串： 
*          shao
*          输入第二个字符串： 
*          shaod 
*          最短编辑距离
*          1 
*
*分析：    （1）选择动态规划的理由：
*          由于该问题是计算最短编辑问题的，要求两个字符串的最短编辑距离时，当     
*          该字符串的子串满足最短编辑距离的时候，那么该字符串也就会满足，但是
*          如何得到子串的最短编辑距离呢？我们可以考虑用回溯法来求，可是回溯法的 
*          缺点是会求出所有可能的路线，当求子串d[i][j]子串的时须求出d[i-1][j-1] 
*          然而该子串d[i-1][j-1] 已经在求d[i-1] [j]的时候求过，用递推的思想还有
*          记忆化的搜索的情况下，我就考虑到了用动态规划。 并且由于该结构具有
*          重叠子问题。再加上所具有的最优子结构。符合动态规划算法基本要素。因此
*          可以使用动态规划算法把复杂度降低到多项式级别。
* 
*          
*          （2）本题思路分析
*          定义两个字符串s1 s2 
*          比较两字符串的某两个相同位置时：（例如s1[i] s2[j] 这时i=j）有三种办法 
*          1.把字符ch1变成ch2， 使得s1与s2字符串在该处相同
*          2.删除s1当中的该字符ch1，使得s1与s2字符串在该处相同 
*          3.插入某个字符ch2，使得s1与s2字符串在该处相同 
*           
*          （3）.首先为了避免重复计算子问题，添加两个辅助数组。
*             <1> 保存子问题结果。
*                 d[ |s1| |s2| ]  其中d[ i  j ] 表示子串 s1（0->i） 与 s2（0->j）
*                 的编辑距离
*             <2> 保存字符之间的编辑距离.
*                 cost 其中 cost= s[ch1] = s[ch2] ? 0 : 1
*          （4）编辑距离的性质
*          计算两个字符串s1+ch1 s2+ch2的编辑距离有这样的性质:
*          <1>.d（s1””） = d（“”s1） = |s1|  当某一个字符串为空时，最短编辑距离
*              是另外一个字符串的长度。    
*              d（“ch1””ch2”） = ch1 == ch2 ? 0 : 1; 当比较两个字符之间的距离
*              时，若两字符相同编辑距离为0，不相同的情况编辑距离为1 
*          <2>.由于我们定义的三个操作来作为编辑距离的一种衡量方法。
*              于是对ch1ch2可能的操作只有
*              1.把ch1变成ch2   因此当ch1==ch2时，d（s1+ch1s2+ch2）  = d（s1s2）
*                                   当ch1!=ch2时，d（s1+ch1s2+ch2）  = d（s1s2）+1 
*              2.s1+ch1后删除ch1              d = （1+d（s1s2+ch2））
*              3.s1+ch1后插入ch2              d = （1 + d（s1+ch1s2））
*              对于2和3的操作可以等价于:
*              2.s2+ch2后添加ch1              d=（1+d（s1s2+ch2））
*              3.s2+ch2后删除ch2              d=（1+d（s1+ch1s2））
*               
*
*              因此：d（s1+ch1s2+ch2） = min（  d（s1s2）+ ch1==ch2 ? 0 : 1 
*                                             d（s1+ch1s2）
*                                             d（s1s2+ch2）  ）;     
*          
*          
*          （5）.新的计算表达式
*              
*              d[ 00