设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符；
！皆为小写字母！
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。
只有一个正整数，为最少字符操作次数。
sfdqxbw gfdgw
4
题解：
用f[i][j]表示a串中前i个字母和b串中前j个字母的最小操作数
有变和不变两种情况
不变：a[i] = b[j]时，f[i][j] = f[i - 1][j - 1];
变：增加：f[i][j] = f[i][j - 1] + 1
减少：f[i][j] = f[i - 1][j] + 1
改变：f[i][j] = f[i - 1][j - 1] + 1
CODE
1 #include <bits/stdc++.h> 2 #define dbug(x) cout << #x << "=" << x << endl 3 #define eps 1e-8 4 #define pi acos(-1.0) 5 6 using namespace std; 7 typedef long long LL; 8 9 const int inf = 0x3f3f3f3f; 10 11 template<class T>inline void read(T &res) 12 { 13 char c;T flag=1; 14 while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)flag=-1;res=c-‘0‘; 15 while((c=getchar())>=‘0‘&&c<=‘9‘)res=res*10+c-‘0‘;res*=flag; 16 } 17 18 const int maxn = 2e5 + 7; 19 20 string a, b; 21 int f[2007][2007]; 22 23 int main() 24 { 25 cin >> a; 26 cin >> b; 27 int lena = a.size(); 28 int lenb = b.size(); 29 for ( int i = 0; i <= lena; ++i ) { 30 f[i][0] = i; 31 } 32 for ( int i = 0; i <= lenb; ++i ) { 33 f[0][i] = i; 34 } 35 for ( int i = 1; i <= lena; ++i ) { 36 for ( int j = 1; j <= lenb; ++j ) { 37 if(a[i - 1] == b[j - 1]) { 38 f[i][j] = f[i - 1][j - 1]; 39 } 40 else { 41 f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1; 42 } 43 } 44 } 45 cout << f[lena][lenb] << endl; 46 return 0; 47 }
原文：https://www.cnblogs.com/orangeko/p/13941802.html