一、问题描述

        最短编辑距离(Minimum Edit Distance)，也被称为Levenshtein距离，是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时，其中编辑单个字符（比如替换、插入、删除）所需要的最少次数。                           简单例子：                                                                                                                                                给定两个单词word1，word2，找到最少的修改操作次数，使得将word1转换成word2，操作包含替换，插入，删除。

        1.替换操作：将某个字符替换成另一个字符

        2.插入操作：在某两个字符中间插入一个新的字符

        3.删除字符：删除某一个字符

        例如，word1=‘ssitten’，word2=‘sitting’，其中最短的编辑操作为

        将 word1 的第一个‘ s ’删除；将‘ e ’替换成‘ i ’；末尾处插入字符‘ g ’，所以编辑距离为3

二、动态规划

        不妨先想一想，两个字符串的最短编辑距离，只需要考虑对其中一个字符串操作即可，所以最短编辑距离的最大值一定不超过两个字符串长度的较大值（只对较短字符串进行替换和插入操作）。                                                                                                                                                         在动态规划思想中，将问题转化成一个个子问题来解决，即如何根据上述三种操作方式推导。定义 F[ i ][ j ] 为字符串1中 1 ~ i 和字符串2 1 ~ j 中的最短编辑距离，将字符串从末尾开始比较有以下递推公式。

        1.当两个字符串末尾相同时 （word1 = "intention’, word2 = ’execution‘ ）

       

                此时不需要任何操作        即可

        2.当两个字符串末尾不相同时，有以下三种操作。

        ① 替换操作 

        直接将 word1 中的末尾字符替换成 word2 中的末尾字符，操作数+1，此时情况为 case1 易理解。

        

        ②插入操作

        在 word1 的末尾后面插入 word2 的末尾字符，操作数+1，举例说明

        例如上述样例    word1=‘ssitten’，word2=‘sitting’   此时在 word1 末尾加上 ‘ g ’ ，word1 和 word2 此时末尾字符相同，即同上述情况相同有

        

        ③ 删除操作

        直接删除 word1 末尾的元素，考虑 F[ i-1 ] [ j ]

        

        再考虑初始条件         

         则递推公式为：

 三、代码部分

        

#include<stdio.h>
#include<string.h>
using namespace std;
#include<iostream> 
int f[2001][2001],n;
char s1[10001],s2[10001];
int main()
{
	scanf("%s",s1);
	scanf("%s",s2);
	int l1=strlen(s1),l2=strlen(s2);
	for(int i=l1-1;i>=0;i--)
		s1[i+1]=s1[i];
	for(int j=l2-1;j>=0;j--)
		s2[j+1]=s2[j];
	for(int i=1;i<=l1;i++) f[i][0]=i;
	for(int i=1;i<=l2;i++) f[0][i]=i;
	for(int i=1;i<=l1;i++)
	for(int j=1;j<=l2;j++)
	{
		if(s1[i]==s2[j])
			f[i][j]=f[i-1][j-1];
		else 
		{
			f[i][j]=min(min(f[i-1][j-1]+1,f[i-1][j]+1),f[i][j-1]+1);  // 替换 删除 插入 
		}
	}
	printf("%d",f[l1][l2]);
	return 0; 
}