时间复杂度n ^ 2
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1010; 4 int n, m; 5 char a[N], b[N]; 6 int dp[N][N]; 7 int main() { 8 cin >> n >> a + 1; 9 cin >> m >> b + 1; 10 for (int i = 0; i <= m; i++) { 11 dp[0][i] = i; 12 } 13 for (int i = 0; i <= n; i++) { 14 dp[i][0] = i; 15 } 16 for (int i = 1; i <= n; i++) { 17 for (int j = 1; j <= m; j++) { 18 dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1); 19 if (a[i] == b[j]) { 20 dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); 21 } else { 22 dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1); 23 } 24 } 25 } 26 cout << dp[n][m] << endl; 27 return 0; 28 }