此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接
https://www.luogu.org/problemnew/show/2758#sub
题目描述
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符；
！皆为小写字母！
输入输出格式
输入格式：
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。
输出格式：
只有一个正整数，为最少字符操作次数。
输入输出样例
输入样例#1：
sfdqxbw
gfdgw
输出样例#1：
4
分析
dp大法好【手动滑稽
好了进入正题
状态：f[i][j]记录ai与bj的最优编辑距离
结果：f[m][n]，其中m、n分别是a、b的串长
初值：b串空，要删a串长个字符；a串空，要插b串长个字符
转移方程：当a[i]=b[j]时，f[i][j]=f[i-1][j-1]，否则，f[i][j]=min(f[i-1][j-1]+1,f[i][j-1]+1,f[i-1][j]+1)
说明：f[i-1][j-1]+1：改a[i]为b[j]；
f[i][j-1]+1：a[i]后插入b[j-1]；
f[i-1][j]+1：删a[i]。
PS：数组一定要开大点，不然会RE后几个点
亲身经历qaq
参考代码
1 #include <cstring> 2 #include <cstdio> 3 int min(int a, int b){ 4 return a < b ? a : b; 5 } 6 int f[5050][50500]; 7 char s1[5050], s2[5050]; 8 int i, j, k, m, n; 9 int main(){ 10 scanf("%s%s", s1, s2); 11 m = strlen(s1); 12 n = strlen(s2); 13 for (i = 1; i <= m; i++) f[i][0] = i; //到i位置为止把字符串A的内容全部删除 14 for (i = 1; i <= n; i++) f[0][i] = i; //在开头给字符串A添上和B到i位置相同的字符 15 for (i = 1; i <= m; i++) 16 for (j = 1; j <= n; j++) 17 if (s1[i - 1] == s2[j - 1]) f[i][j] = f[i - 1][j - 1]; 18 else f[i][j] = min(min(f[i - 1][j],f[i][j - 1]), f[i - 1][j - 1]) + 1; 19 printf("%d ", f[m][n]); 20 return 0; 21 }