超级经典的DP例题 基础班例题 Pdp笔记31

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size(), m = b.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        // f[0][0] = 0;
        for (int i = 0; i <= n; i ++) f[i][0] = i;
        for (int j = 0; j <= m; j ++) f[0][j] = j;
        for (int i = 1; i <= n; i ++) 
            for (int j = 1; j <= m; j ++) {
                // f[i][j] = f[i - 1][j - 1] + (a[i - 1] != b[j - 1]);
                // f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                // f[i][j] = min(f[i][j], f[i][j - 1] + 1);
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
                if (a[i - 1] != b[j - 1]) f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
                else f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            }
        return f[n][m];
    }
};