72.编辑距离(递推)

递推版本: f[i+1][j+1] word1前i+1个字符转化成word2前j+1个字符所需的最小操作数 操作都只对word1操作 插入操作: 插入的字符将j+1给抵消掉了, 所以情况变成了f[i+1][j]+1 删除操作: 删除了一个字符, i+1被删了, f[i][j+1]+1 修改操作: i+1和j+1都被抵消掉了

class Solution {
    /**
     * 递推版本: f[i+1][j+1] word1前i+1个字符转化成word2前j+1个字符所需的最小操作数
     * 操作都只对word1操作
     * 插入操作: 插入的字符将j+1给抵消掉了, 所以情况变成了f[i+1][j]+1
     * 删除操作: 删除了一个字符, i+1被删了, f[i][j+1]+1
     * 修改操作: i+1和j+1都被抵消掉了
     */
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        // f[i+1][j+1] word1前i+1个字符转化成word2前j+1个字符所需的最小操作数
        int[][] f = new int[n+1][m+1];
        // f[0] 是有一边不存在的时候, 对应递归的 j = -1
        for (int i = 0; i < m ; i++) {
            f[0][i+1] = i + 1;
        }
        // 还是采用递归的思路理解
        for (int i = 0; i < n; i++) {
            f[i+1][0] = i + 1;
            for (int j = 0; j < m; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    f[i+1][j+1] = f[i][j];
                } else {
                    f[i+1][j+1] = Math.min(f[i][j]+1, Math.min(f[i][j+1], f[i+1][j]) + 1);
                }
            }
        }

        return f[n][m];

    }
}