线性DP

状态表示: f[i][j]所有将a[1 - i]变成b[1 - j]的操作步数 的最小值

状态转移：

考虑最后一步操作，最后一步操作一共有三种

则状态方程为： f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1, f[i -1][j - 1]) + 1

$ 时间复杂度O(N^2)，空间复杂度O(N^2) $

参考文献

算法基础课

AC代码

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size();
        int m = b.size();
        a = ' ' + a;
        b = ' ' + b;
        vector<vector<int>> f(max(n, m) + 1, vector<int>(max(n, m) + 1));
        //初始化其中字符串为空，则需要增i次/删除i次
        for (int i = 0 ; i <= n ; i ++) f[i][0] = i;
        for (int i = 0 ; i <= m ; i ++) f[0][i] = i;

        //DP
        for (int i = 1 ; i <= n ; i++){
            for (int j = 1 ; j <= m ; j ++){
                f[i][j] = min(f[i - 1][j] , 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);
            }
        }

        return f[n][m];
    }
};