1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=2000; 4 char c1[N],c2[N]; 5 int n,m,f[N][N]; 6 int main() { 7 scanf("%d", &n); 8 scanf("%s", c1 + 1); 9 scanf("%d", &m); 10 scanf("%s", c2 + 1); 11 for (int i = 1; i <= n; i++) { 12 f[i][0] = i; 13 } 14 for (int i = 1; i <= m; i++) { 15 f[0][i] = i; 16 } 17 for (int i = 1; i <= n; i++) { 18 for (int j = 1; j <= m; j++) { 19 f[i][j] = min(f[i - 1][j]+1, f[i][j - 1]+1); 20 if (c1[i] == c2[j]) { 21 f[i][j] = min(f[i][j], f[i - 1][j - 1]); 22 } else { 23 f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); 24 } 25 } 26 } 27 printf("%d ",f[n][m]); 28 }