最短编辑距离（动态规划超详细填表法）

链接：https://www.nowcoder.com/questionTerminal/9649617be3bf42288f50758df4310655
来源：牛客网
 

UNIX系统下有一个行编辑器ed，它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作。例如某一行的内容是“ABC”，经过把第二个字符替换成“D”、删除第一个字符、末尾插入一个字符“B”，这三步操作后，内容就变成了“DCB”。即“ABC”变成“DCB”需要经过3步操作，我们称它们的编辑距离为3。

现在给你两个任意字符串（不包含空格），请帮忙计算它们的最短编辑距离。

思路分析：

此题是一道动态规划类的题目，这类题目不是特别的难，下面分享一下我的做题思路。

拿到一道动态规划类的题目要做的有三件事：

1、阅读理解题目，并且简化问题。

2、设定初始值，填表。

3、在表格的数据当中寻找规律。

由于动态规划类的题目，它的下一个结果仅仅取决于上一次填表的结果，这样一层一层迭代下来最终就能得到想要的结果。填表的过程要严格遵循题目指定的规则。

我们来看这道题的表格：

 

一般初值的设定不是一成不变的，需要根据题目来自己尝试，并不是一次就能成功的所以有时候需要一点灵感。可以看到我用颜色标记出来的是设定的初值。填完表之后，在表中找规律，发现要是正好在对角线上的两个字符相等那么就取它左上角的数字。要是不相同就去它上面、左面、左上的元素中最小值再加1，在表的右下角就是最终的结果。

在填表的时候要填什么数字完全是按照规则来的，填完之才能够找规律。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/* 它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作 */
int deal_shortest(string str1, string str2)
{
	int len1 = str1.size();
	int len2 = str2.size();
	int i = 0;
	int j = 0;
	vector<vector<int>> m_v(len1+1,vector<int>(len2+1,0));//生成二维数组用于填表
	/* 设定初始值 ,vector一旦设定存储空间那么它就成了C语言中的数组，存在边界*/
	m_v[0][0] = 0;
	for (i=1;i<=len1;++i)
	{
		m_v[i][0] = i;
	}
	for (i=1;i<=len2;++i)
	{
		m_v[0][i] = i;
	}
	for (i=1;i<=len1;++i)
	{
		for (j=1;j<=len2;++j)
		{
			if (str1[i-1]==str2[j-1])
			{
				m_v[i][j] = m_v[i - 1][j - 1];
			}
			else
			{
				m_v[i][j] = min(m_v[i][j - 1], min(m_v[i - 1][j - 1], m_v[i - 1][j]))+1;
			}
		}
	}
	return m_v[len1][len2];
}
int main()
{
	string str1;
	string str2;
	while (cin>>str1>>str2)
	{
		cout<<deal_shortest(str1, str2)<<endl;
		str1.clear();
		str2.clear();
	}
	system("pause"); 
	return 0;
}