[MIku]（https://www.luogu.com.cn/problem/P2758）

定义$dp{i,j}$为把$A{1-i}$变为$B_{1-j}$得最小花费

可以由$dp{i-1,j}$转移，把$A{i}$删了

$dp{i,j-1}$ 最后加个$B{j}$

$dp_{i-1,j-1}$ 把$A_i$改成$B_j$并且显然，若他们相等，就不用操作

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
string a,b;
int dp[2001][2001];
int la,lb;
int c;
int main(){
    cin>>a>>b;
    la=a.length();
    lb=b.length();
    c=max(la,lb);
    for(int i=1;i<=c;++i){
        dp[i][0]=dp[0][i]=i;
    }
    for(int i=1;i<=la;++i){
        for(int j=1;j<=lb;++j){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
            }
        }
    }
    cout<<dp[la][lb];
    return 0;
}