文件名称：动态规划—最短编辑问题—（非常详细分析以及代码）
文件大小：6KB
文件格式：CPP
更新时间：2014-06-27 02:42:47
该内容是算法作业的报告，因此附有几百字的分析和详细解释，可运行
*问题描述：设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 * 请按任意键继续. . .