经典线性dp的字符串类型的问题，配合详细注释

最短编辑距离

此题目与最长公共子序列的思路相似，可以对比

最长公共子序列

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N]; //表示从a[1~i]变成b[1~j]的所有操作中的最小次数的集合
char a[N],b[N]; //表示两个字符串
int n,m;
int main()
{
    scanf("%d%s",&n,a+1);  //下标为1读入字符串，便于处理
    scanf("%d%s",&m,b+1);
    //从a的前0个字母变成b的前j个字母，只能选择添加，添加的个数就是b的长度
    for (int j=0;j<=m;j++) f[0][j]=j; 
    //从a的前n个字母变成b的前0个字母，只能选择删除，删除的个数是a的长度
    for (int i=0;i<=n;i++) f[i][0]=i;

    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][j],f[i-1][j-1]);
            //如果当前的两个字母不等，则需要既保证前面的所有字母分别相等，同时改当前字母
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    printf("%d\n",f[n][m]);  //答案就是使a的前n个字符与b的前m个字符相等所需要操作的最小次数
    return 0;
}