代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int dp[N][N];
char a[N], b[N];

int main(){
    int n, m;
  cin>>n>>a+1>>m>>b+1;
    for(int i = 1; i <= m; i++) dp[0][i] = i;
    for(int i = 1; i <= n; i++) dp[i][0] = i;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    cout<<dp[n][m];
    return 0;
}

核心

DP