3062: 计算字符串距离

解题思路:f[i][j]表示a字符串前i字符与b字符串前j字符最短距离

注意事项:

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
int f[N][N];
string a,b;
int main()
{
	int n;
	cin >> n;
	while(n --){
		cin >> a >> b;
		memset(f, 0, sizeof f);
		for(int i = 1; i <= a.size(); i ++) f[i][0] = i;
		for(int i = 1; i <= b.size(); i ++) f[0][i] = i;
		for(int i = 1; i <= a.size(); i ++)
			for(int j = 1; j <= b.size(); j ++){
				if(a[i-1] == b[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[a.size()][b.size()] << endl;
	}
	return 0;
}