文档介绍：课程名称：动态规划——编辑距离问题
-2-
-6-
《算法设计与分析》课程报告
课题名称： 动态规划--编辑距离问题
课题负责人名（学号）：
同组成该如何变化以及变化的最短距离。
具体来说，首先选用数组a1存储字符串A(设长度为n)，a2存储字符串B(设长度为m），d矩阵来进行具体的运算；这里有两个特殊情况比较简单可以单独考虑，即A的长度为0而B不为0还有A不为0B为0，这两种情况最后的编辑距离分别为m和n;讨论一般情况，d矩阵为d［n][m］,假定我们从d[0]［0］开始一直进行以下操作到了d［i］［j］的位置，其中删除操作肯定是A比B长,同理，插入字符操作一定是A比B短，更改字符操作说明一样长，我们所要做的是对d[i][j
课程名称：动态规划——编辑距离问题
-2-
-3-
—1] d[i—1］［j］ d[i-1］［j-1］所存数进行比较，其中最小的即为当前长度和样式的字符串A变为B的编辑距离,依次这样计算到最后的d［n］[m]中所存的数即为最终的编辑距离。
三、证明
1、理论前提:动态规划的基本思想与分治法类似,也是将待求解的问题分解成若干份的子问题，先分别解决好子问题，然后从子问题中得到最终解。但动态规划中的子问题往往不是相互独立的，而是彼此之间有影响。该算法的有效性依赖于两个重要的性质:最优子结构性质和问题重叠性质。
最有子结构性：以自底向上的方法递归地从子问题的最优解逐步构造出整个问题的最优解。
重叠子问题性:每次产生的子问题并不总是新问题，利用动态规划对每一个子问题只解一次,并将其存入表格中，下次用到该子问题的解时,只要查找表格即可。
2、本题：本题首先符合最优子结构性，即让字符串A从1开始递增到最终长度n，也就是从只有一个字符开始计算，每增加一个字符计算一次，符合自底向上的方法递归地解决子问题；其次符合重叠子问题性，每增加一个字符计算的时候总要用到前一状态时的编辑距离，并且本题我采用了矩阵来存储旧子问题的数据，都只计算了一次，所以也符合.
3、总结：综上两点，可知本题采用了动态规划的思想来解决，并能得到正确的答案。
四、代码及解释(注释)
#include〈>
＃include<fstream〉
＃include<stdlib。h>
#include<string。h>
using namespace std;
const int MAX=1000;
课程名称：动态规划——编辑距离问题
-2-
-4-
int min(int a，int b)
{
if（a〉=b）
return b;
else
return a；
｝
int main（)
{
int d［MAX］［MAX］;
int i,j;
char a1[MAX]， a2[MAX];
FILE ＊fp;
fp=fopen(""，”r"）;
fscanf（fp,”%s"，a1)；
fscanf（fp，"%s"，a2)；
fclose（fp）；
int n=strlen（a1)—1； //字符串末尾多1
int m=s