莫欺少年穷，修仙之旅在这开始—>算法基础课题解

思路：

1. f[i][j] 表示 a[1~i] 转换成 b[1~j] 的最少操作数
2. 状态转移有三种操作：删除，插入，替换
3. 删除：f[i-1][j] + 1
4. 插入：f[i][j-1] + 1
5. 替换：若a[i] == b[j]，则 f[i-1][j-1]；否则，f[i-1][j-1] + 1
6. 最后，f[i][j] = min{f[i-1][j] + 1, f[i][j-1] + 1, f[i-1][j-1] + (a[i] != b[j])}

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    cin>>n>>a+1>>m>>b+1;

    for(int i=1;i<=n;i++) f[i][0]=i; //删除

    for(int i=1;i<=m;i++) f[0][i]=i; //插入

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=min(min(f[i-1][j],f[i][j-1])+1,f[i-1][j-1]+(a[i]!=b[j]));

    cout<<f[n][m]<<endl;

    return 0;
}