luoguP2758

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=30+5,INF=0x3f3f3f3f,MOD=1e9+7;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
typedef long long LL;
string a,b;
int lena,lenb,k;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>a>>b;
	lena = a.size(),lenb = b.size();
	a = " "+a,b = " "+b;
	vector<vector<int>>dp(lena+1,vector<int>(lenb+1));
	for(int i=0;i<=lena;i++)dp[i][0] = i;
	for(int i=0;i<=lenb;i++)dp[0][i] = i;
	for(int i=1;i<=lena;i++){
		for(int j=1;j<=lenb;j++){
			k = 1;
			if(a[i]==b[j])k = 0;
			dp[i][j] = min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+k});
		}
	}
	cout<<dp[lena][lenb];
	return 0;
}

wy

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#define FORa(i,s,e) for(int i=s;i<=e;i++)
#define FORs(i,s,e) for(int i=s;i>=e;i--)

using namespace std;

const int N=2000;
string sta,stb;
int m,n,f[N+1][N+1];//f[i][j]字符串sta(sta[0]-sta[i-1])转化到字符串stb(stb[0]-stb[j-1])的最短编辑距离
inline int min(int a,int b){return a<b?a:b;}
int main()
{
cin>>sta>>stb;
n=sta.size(),m=stb.size();
memset(f,127/3,sizeof(f));
FORa(i,1,n) f[i][0]=i;
FORa(i,1,m) f[0][i]=i;
f[0][0]=0;//注意边界与初值，当两字符串中存在空串处理
FORa(i,1,n)
FORa(j,1,m)
if(sta[i-1]==stb[j-1]) f[i][j]=f[i-1][j-1];//当当前字符相同 ，答案等于之前每个减一位的答案
else f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
//f[i-1][j-1]表示把sta[i-1]改成stb[j-1] f[i-1][j]表示把字符串sta中的sta[i]删除 f[i][j-1]表示字符串sta后插入stb[j]
printf("%d",f[n][m]);
return 0;
}