牛客题霸 -- HJ52 计算字符串的编辑距离

解题步骤：

参考代码：

int main()
{
	string s1;
	string s2;
	while (cin >> s1 >> s2)
	{
		int m=s1.size();
		int n=s2.size();
		//增加空白字符，修正下标的映射关系
		s1=' '+s1;
		s2=' '+s2;
		//多卡一行，多开一列
		vector<vector<int>> dp(m+1,vector<int>(n+1));
		//初始化
		for(int i=0;i<=m;i++)
		{
			dp[i][0]=i;
		}
		for(int j=0;j<=n;j++)
		{
			dp[0][j]=j;
		}
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
			{
				//状态转移方程
				if(s1[i]==s2[j])
				{
					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[m][n]<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

你学会了吗？？？