会计学例如，字符串A:AGTAAGTAGGC转换为字符串B:AGTCTGACGC。操作一：A串：AGTAAGT*AGGCB串：AGT*C*TGACGC需要5步操作（2次删除，2次修改，1次删除）操作二：A串：AGTAAGTAGGCB串：AGTCTG*ACGC需要4次操作（3次修改，1次删除）我们计算的编辑距离是变换(biànhuàn)的最小步数，所以要取其中的最小值。（3）可以修改字符A[i]，使它变为B[j]，若A[i]=B[j]，修改其实相当于用了0步；若A[i]!=B[j]，修改相当于用了1步。所以dp[i][j]=dp[i-1][j-1]+（A[i]==B[j]?0：1）。最后的dp[i][j]就是(jiùshì)选择上述3种状态转移中的最小值。综上所述，状态转移方程dp[i][j]可归结为如下情况：(1)当两个字符相同，即A[i]=B[j]时，dp[i][j]=min{dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]}(2)当两个字符不同，即A[i]!=B[j]时，dp[i][j]=min{dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1}需要注意(zhùyì)的是，要对dp[0][0:m]，dp[0:n][0]进行初始化。*dp[0][i],就是说A串是一个空串，而B串是个长度为i的串，很显然A串变为B串就是插入i个字符，即dp[0][i]=i。*dp[i][0]，就是说A串是个长度为i的串，而B串是一个空串，很显然A串变为B串就是删除i个字符，即dp[i][0]=i。根据上述分析，编辑最短距离的算法可描述如下：intDP(char*s1,char*s2){inti,j,m=strlen(s1),n=strlen(s2),tem;//初始化for(i=0;i<=n;i++)dp[0][i]=i;//从0个字符转换为i个字符，需要(xūyào)插入i次一重循环时间复杂度为T(n)for(i=0;i<=m;i++)dp[i][0]=i;//从i个字符转换为0个字符，需要(xūyào)删除i次一重循环时间复杂度为T(m)//用动态规划方法计算编辑距离for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(s1[i-1]==s2[j-1])tem=dp[i-1][j-1];//当两个字符(zìfú)相同时，替换操作代价为0，直接将dp[i-1][j-1]转移过来elsetem=dp[i-1][j-1]+1;//当s1[i-1]!=s2[j-1]时,替换操作代价为1tem=min(tem,dp[i][j-1]+1);//dp[i][j-1]+1为在s1的i+1位置上插入字符(zìfú)s2[j]tem=min(tem,dp[i-1][j]+1);//dp[i-1][j]+1为在s1的i位置上删除字符(zìfú)s1[i]dp[i][j]=tem;//dp[i][j]取3种状态的最小值}returndp[m][n];//返回dp[m][n]}二重循环：时间复杂度为T(n*m)时间复杂度：总的时间复杂度为T(n*m+n+m)=O(m*n)最坏的时间复杂度为O(n^2)运行(yùnxíng)结果示例：Theend,thankyou!