# 2857. 编辑距离

//状态 dp[i][j]表示a的前i位变成b的前j位所要的最少时间
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[502][502];

string a, b;
int main() {
int n;
cin >> n;
while (n--) {
fill(dp[0], dp[0] + 502 * 502, 0);
for (int i = 0; i < 502; ++i) {
dp[i][0] = i;
dp[0][i] = i;
}
cin >> a >> b;
for (int i = 1; i <= a.size(); ++i) {
for (int j = 1; j <= b.size(); ++j) {
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
cout << dp[a.size()][b.size()] << endl;
}
return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
int N;
cin >> N;
while (N--) {
string A, B;
int ld[501][501];
cin >> A >> B;
for (int i = 0; i <= A.length(); i++) {
ld[0][i] = i;
}
for (int i = 0; i <= B.length(); i++) {
ld[i][0] = i;
}
for (int x = 1; x <= B.length(); x++) {
for (int y = 1; y <= A.length(); y++) {
if (A[y - 1] == B[x - 1]) {
ld[x][y] = ld[x - 1][y - 1];
} else {
ld[x][y] = min(ld[x - 1][y], min(ld[x][y - 1], ld[x - 1][y - 1])) + 1;
}
}
}
cout << ld[B.length()][A.length()] << endl;
}
return 0;
}


### include

int minIN3(int a,int b,int c){
int min = (a<b)?a:b;
return (min<c)?min:c;
}
int main(){
char * a = (char)malloc(sizeof(char)500);
char * b = (char)malloc(sizeof(char)500);
a[0] = ‘ ‘;//首字符置为空格，方便dp[0][0]初始化
b[0] = ‘ ‘;
int N;
scanf(“%d”,&N);
getchar();
for(int i =0;i<N;i++){
gets(a+1);
gets(b+1);
int aLen = strlen(a);
int bLen = strlen(b);
int edit[bLen][aLen];
for(int i = 0 ;i<aLen;i++){
edit[0][i] = i;
}
for(int j = 0 ;j<bLen;j++){
edit[j][0] = j;
}
int i ;
for( i =1;i<bLen;i++){
for(int k = 1;k<aLen;k++){
edit[i][k] = minIN3(edit[i-1][k]+1,edit[i][k-1]+1,edit[i-1][k-1]+((a[k]==b[i])?0:1));//状态转移方程
}
}
printf(“%d\n”,edit[bLen-1][aLen-1]);

}


}

### include

using namespace std ;

int num [501][501] ;
int main (){
int T ,i ;
cin >> T;
for (i =0;i > a >> b;
int lena = a.length () ;
int lenb = b.length () ;
int j,k ;
for (j =0;j <=lenb;j ++)
num [j][0] = j ;
for (k =0;k <=lena;k ++)
num [0][k] = k ;
for (j=1;j <=lenb;j ++){
for (k =1;k <=lena;k ++){
if (a[k-1] == b [j-1])
num [j][k] = num [j-1][k-1];
else {
int c = min (num[j-1][k],num[j][k-1]);
int d = min (c,num[j-1][k-1]) ;
num [j][k] = d +1;
}
}
}
cout << num [lenb][lena] << endl ;
}
}

#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<utility>
#include<cassert>
#include<climits>
using namespace std;

int main()
{
#ifdef debug
freopen("testdata.in", "r", stdin);
freopen("testdata.out", "w", stdout);
#endif
int T;
char str1[501], str2[501];
scanf("%d", &T);
unsigned editdistance[503];
memset(editdistance, 0, sizeof(editdistance));
while(T--)
{
scanf("%s%s", str1, str2);
const unsigned size1 = strlen(str1);
const unsigned size2 = strlen(str2);

// When looking at the first char of str1.
for(unsigned i = 1; i <= size2; i++)
editdistance[i] = i;

// Dynamic Programming
for(unsigned i = 1; i <= size1; i++)
{
// Looking at the first char of str2
editdistance[0] = i;
unsigned ij = i - 1;
for(unsigned j = 1; j <= size2; j++)
{
if(i - 1 < size1 && j - 1 < size2 && str1[i-1] != str2[j-1]) ij++;
int a = min(min(editdistance[j-1], editdistance[j]) + 1, ij);
ij = editdistance[j];
editdistance[j] = a;
}
}
printf("%u\n", editdistance[size2]);
}
return 0;
}