正经题解

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
long long l1,l2,dp[2005][2005];
int main(){
	cin>>s1>>s2;
	l1 = s1.size();
	l2 = s2.size();
	for(int i = 0;i <= l1;i++){
		dp[i][0] = i;
	}
	for(int i = 0;i <= l2;i++){
		dp[0][i] = i;
	}
	for(int i = 1;i <= l1;i++){
		for(int j = 1;j <= l2;j++){
			if(s1[i - 1] == s2[j - 1]){
				dp[i][j] = dp[i - 1][j - 1];
			}else{
				dp[i][j] = min(dp[i - 1][j],min(dp[i][j - 1],dp[i - 1][j - 1])) + 1;
			}
		}
	}
	cout<<dp[l1][l2];
	return 0;
}