优题解：AcWing 902. 最短编辑距离 - AcWing
一共有三个操作方式：
1.删除操作：插入操作之前即前 i - 1 个和 前 j 已经排好 即 f[i-1][j] + 1 ;
2.插入操作：删除操作之前即前 i 个和 前 j - 1 个已经拍好即 f[i][j-1] + 1 ;
3:替换操作： 替换操作之前即前 i-1 个和前 j-1个已经排好
这时候又要分成两种情况：1.a[i]和b[j] 相同 则f[i-1][j-1]
2.a[i]和b[j] 不相同则 f[i-1][j-1] + 1
下面是一些细节问题，不想一一再过了： 
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 1010 ,INF = 1e9 ;; int f[N][N] ; char a[N] , b[N] ; int n,m ; int main(){ cin >> n >> a+1 ; cin >> m >> b+1 ; for(int i = 1 ;i <= n ; i++ ) f[i][0] = i ;//第二个字符串长度为0 即将第一个字符串全部删除 for(int i = 1 ;i <= m ; i ++) f[0][i] = i ;//第一个字符串长度为0 即全部插入和第二个字符串删除的 for(int i = 1 ; i<= n ; i ++){//遍历第一个字符串， for(int j = 1 ; j <= m ; j ++){//遍历第二个字符串，当两个字符串出现一样的时候就可以进行特殊处理 f[i][j] = min(f[i-1][j]+1,f[i][j-1] + 1) ; if(a[i]==b[j]) f[i][j] = min(f[i-1][j-1] , f[i][j]) ; else f[i][j] = min(f[i-1][j-1] + 1 , f[i][j]); } } cout << f[n][m] << endl ; return 0 ; }
