（2014复旦机试）字符串的编辑距离

问题分类：动态规划

问题描述：

把两个字符串变成相同的三个基本操作定义如下：

1. 修改一个字符（如把a变成b）
2. 增加一个字符(如abed 变成abedd)
3. 删除一个字符（如jackbllog 变成jackblog）

• 针对于jackbllog到jackblog只需要删除一个或增加一个l 就可以把两个字符串变为相同。
• 把这种操作需要的最小次数定义为两个字符串的编辑距离L。
• 编写程序计算指定文件中字符串的距离。输入两个长度不超过512字节的ASCII字符串，在屏幕上输出字符串的编辑距离。

算法思路

思路与最长公共子串相似（但需要对dp数据进行一些优化）:

dp[i][j]：即在字符串1的i位置，字符串2的j位置时最小的编辑距离

str1[i] == str2[j]时，dp[i][j] = dp[i-1][j-1];

str1[i] != str2[j]时，三种情况的解释如下:

• alter str1[i]、str2[j]
• delete str1[i] or add str2[j]
• delete str2[j] or add str1[i]

#include<iostream>
#include<vector>
using namespace std;
/*
a b
*/
int main() {
	string s1, s2;
	cin >> s1 >> s2;
	int n1 = s1.size();
	int n2 = s2.size();
	s1 = " " + s1;
	s2 = " " + s2;
	vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
	//边界条件初始化
	for (int i = 1; i <= n1; i++) {
		dp[i][0] = i;
	}
	//边界条件初始化
	for (int i = 1; i <= n2; i++) {
		dp[0][i] = i;
	}
	//dp过程
	for (int i = 1; i <= n1; i++) {
		for (int j = 1; j <= n2; j++) {
			if (s1[i] == s2[j]) {
				//如果i，j位置上的字符相等
				dp[i][j] = dp[i - 1][j - 1];
			}
			else {
				//如果i，j位置上的字符不相等
				dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
			}
		}
	}
	cout << dp[n1][n2] << endl;
}