线性DP：$O(nm)$;

思路

• 第一类：
• 第i个和第j个相等
  min(dp[i,j],dp[i-1,j-1])

• 第i个和第j个不相等
  min(dp[i,j],dp[i-1,j-1]+1)

• 第二类：

• 前i-1个 和 前j个 相等，那么只需要将i删掉即可
  min(dp[i,j],dp[i-1,j]+1)

• 前1个 和 前j-1个 相等，那么只需要将j删掉即可
  min(dp[i,j],dp[i,j-1]+1)

• 预处理

• 0和前j个字符比较，有j次插入 dp[0,1~j] = j;
• 前i个字符和0比较，有i次插入 dp[1~i,0] = i;

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 3010;
int dp[N][N];
char a[N],b[N];

int main()
{
    scanf("%s%s",a+1,b+1);

    int n = strlen(a+1) , m = strlen(b+1);
    for(int i=0;i<=m;++i) dp[0][i] = i;
    for(int i=0;i<=n;++i) dp[i][0] = i;

    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1);
            if(a[i] == b[j]) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);
            else dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}