状态转移方式与二维相同，使用pre来记录f[i-1][j-1]的值

C++ 代码

#include <iostream>
using namespace std;

const int N = 1010;
char w1[N], w2[N];
int n, m;
int f[N];

int main()
{
    cin >> n >> w1 + 1;
    cin >> m >> w2 + 1;
    // 初始化f[i]相当于初始化f[0][i]
    for (int i = 0; i <= m; ++i) f[i] = i;

    for (int i = 1; i <= n; ++i)
    {
        // pre初始化为前一轮的f[0]也就是f[i-1][0]
        // pre中存放的是前一轮的f[i-1][j-1]
        int pre = f[0];
        // 更新当前轮f[0]也就是f[i][0]
        f[0] = i;
        for (int j = 1; j <= m; ++j)
        {
            // 记录更新前的f[j]也就是f[i-1][j]
            int tmp = f[j];
            if (w1[i] == w2[j]) f[j] = pre;
            else
            {
                f[j] = min(pre, min(f[j], f[j - 1])) + 1;
            }
            // 将pre的值更新，使得到达下一个j时,它存放的值为f[i-1][j-1]
            pre = tmp;
        }
    }

    cout << f[m] << endl;
    return 0;
}