481
spoj EDIST dp string distance
https://www.spoj.com/problems/EDIST/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int f[2002][2002];
char a[2002], b[2002];
int main(){
int t;
scanf("%d", &t);
while (t--){
memset(f, 127 / 3, sizeof(f));
scanf("%s%s", a, b);
int n = strlen(a), m = strlen(b);
for (int i = 0; i < n; i++) f[i][0] = i;/////
for (int i = 0; i < m; i++) f[0][i] = i;/////
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; 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;
}
printf("%d\n", f[n][m]);
}
return 0;
}最后更新：2017-08-28 09:03:16