信息学奥赛一本通T1276 -编辑距离

解题思路:f[i][j]表示i长度的字符串变化到j长度字符串的最短距离

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N = 2e3 + 10;
int f[N][N];
int main()
{
	string s1, s2;
	cin >> s1 >> s2;
	
	for(int i = 1; i <= s1.size(); i ++) f[i][0] = i;
	for(int i = 1; i <= s2.size(); i ++) f[0][i] = i;
	for(int i = 1; i <= s1.size(); i ++)
		for(int j = 1; j <= s2.size(); j ++)
		{
			if(s1[i-1] == s2[j-1]) 
				f[i][j] = f[i-1][j-1];
			else
				f[i][j] = min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1]) + 1; 
		}
	cout << f[s1.size()][s2.size()];
	return 0;
}