ACWing902. 最短编辑距离

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int dp[N][N];
int la;
string a;
int lb;
string b;
int main(){
    cin>>la;
    cin>>a;
    cin>>lb;
    cin>>b;
    for(int i=0;i<=la;i++){
        dp[i][0]=i;
    }
    for(int i=0;i<=lb;i++){
        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(dp[i-1][j]+1,dp[i][j-1]+1);
            dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    cout<<dp[la][lb];
}