咱这里直接把代码贴出来，造福各位同学
解析在后面
#include <iostream>
#include <string>
using namespace std;
const int Max = 1000;
char a[Max],b[Max];
int f[Max][Max];
int m , n;
int main (void) {
int n , m ;
cin>>n>>m>>a+1>>b+1;
for (int i = 0; i <=m; i++) {//colmn 0 and row 0 means the NULL transforms into the target string.
f[i][0]=i;
}
for (int j = 0; j <=n; j++) {
f[0][j]=j;
}
/*the equation: f(x,y)= {
colmn 0 and row 0 = i or j , i=0 or j = 0;
min( f(i-1,j)+1, f(i,j-1)+1, f(i-1,j-1)+1 ), a[i]!=b[j];
f(i-1,j-1), a[i]=b[j];*/
for (int i = 1; i <=m ; i++) {
for (int j = 1; j <=n ; j++) {
if (a[i] == b[j]) {
f[i][j] = f[i-1][j-1];
}else {
f[i][j] = min(min( f[i-1][j] + 1, f[i][j-1] + 1), f[i-1][j-1] + 1);
}
// one more concise syntax: f[i][j] = min(min( f[i-1][j] + 1, f[i][j-1] + 1), (a[j] == b[i] ? f[i-1][j-1] : f[i-1][j-1] + 1));
}
}
cout<<f[m][n]<<endl;
return 0;//the core is that the last step to complete the transformation only has 3 methods.delete(^),insert(<<) or replace(i-1,j-1)+1;
//if in the last step,the a[i],b[j], happen to corresponde to each other, there is no need to add an manipulation.
}
咱在抄的时候把注释去掉。再把编程风格换成属于自己的类型就可以了。其中最核心的代码其实只有一行（注释内的那行代码）或者四行
空行
解析：其实就是路径题目从左上到右下的变种而已
第一步，确定最后一步。最后完成的状态一定是恰好使得a[i]=b[j]即两个字符串相等。 那么他前面所有步骤也一定是最优的解。所以可以放心大胆的去回推。那么操作方法有且仅有三个，删插换。那么三种方法通向最后一步，一定使用二维数组存储，不然一维无法从三条路通往最后一步。这里设为存储数组为f[x][y]. 1111 a(j)------> b(i) | | v
盗一张图
若前一步走的是1，则相当于是b串删除了一个数（i的行数增多了，4个字符变为5个，那么就要删掉一个）
若从【3】【5】走到【4】【5】（注意是数组下标，不是坐标），
本来之前是最优解，人家好好的，
你b串多了一个d，那么就得把你删了
若走的是2，则是b串插入了一个数，
若从【4】【4】走到【4】【5】，本来是最优解，但a串突然多了个e
那b串肯定也得跟上，插入一个e啊
若走的是3，则是做了替换操作
若从【3】【4】走到【4】【5】，也就是a,b同时加了一个字符，
那么这时候不需要删插，只需要变换即可解决。
但是从3走还有个问题，你若是同时增加了一个相同的字符，就不需要做任何操作了呀。所以要加判断，如果两个字符相同，就不需要执行 操作数+1 的动作。
第二步，列出转移方程：取三种走路方法中的最优（也就是操作次数最少的那一个）解
the equation: f(x,y)=
min( f(i-1,j)+1, f(i,j-1)+1, f(i-1,j-1)+1 ), a[i]!=b[j];
f(i-1,j-1), a[i]=b[j];
第三步 初始条件
初始条件想都不用想肯定有一个 f[0][0]=0;此外，所有下标为0的，都是算在转移方程中不出来的，所以这些我们也要手动赋初值。 初值参考上面的那张表格。
for (int i
= 0; i
<=m
; i
++) {
f
[i
][0]=i
;
}
for (int j
= 0; j
<=n
; j
++) {
f
[0][j
]=j
;
}
最后大功告成结束啦
