这题最重要的就是找到状态转移方程

#include<bits/stdc++.h>
using namespace std;
long long l1,l2,dp[2005][2005];
string s1,s2;
int main()
{
	cin>>s1>>s2;
	l1=s1.length();//字符串s1的长度
	l2=s2.length();//字符串s2的长度
	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];//状态转移方程1
			}
			else
			{
				dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;//状态转移方程2
			}
		}
	}
	cout<<dp[l1][l2]<<endl;
	return 0;
}