$$ 动态规划 \begin {cases} 状态表示 f(i, j) \begin {cases} 集合：所有将A[1..i]变成B[1..j]的操作方式\\\ 属性：操作次数最小 \end{cases}\\\ \\\ 状态计算 \begin {cases} 分类 \begin {cases} 最后一步删掉A[i] & 那么当前 i=j+1，在此之前需要把A[1..i-1]变成B[1..j] \\\ \\\ 最后一步在A[i]后插入B[j] & 那么当前 i=j-1，在此之前需要把A[1..i]变成B[1..j-1] \\\ \\\ 最后一步改A[i] & 那么当前 i=j，在此之前需要把A[1..i-1]变成B[1..i-1] \\\ \end {cases} \\\ \\\ 求解：三种情况的min \end{cases}\\\ \end {cases} $$

#include <iostream>
using namespace std;

const int N = 1010;

int f[N][N];
char a[N], b[N];
int n, m;

int main()
{
    cin >> n >> a + 1 >> m >> b + 1;

    // 初始化
    for (int j = 0; j <= m; j ++) f[0][j] = j;  // 将空串a变为b[1..j]需要插入j次
    for (int i = 0; i <= n; i ++) f[i][0] = i;  // 将a[i..i]变为空串b需要删除i次

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