class Solution {
    public int minDistance(String s, String p) {
        int m = s.length(), n = p.length();
        if(s == null && p == null) return 0;
        s = " " + s;
        p = " " + p;
        int[][] f = new int[m+1][n+1];
        // f[0][i]表示空串S到p[i]需要操作的最小次数
        for(int i = 1; i <= n; i++){
            f[0][i] = i;
        }
        // f[i][0]表示串S到空串P需要操作的最小次数
        for(int i = 1; i <= m; i++){
            f[i][0] = i;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果s的第i个==p的第j个字符, f[i][j]意味着s[0,i] == p[0,j], 即s[0,i-1] == p[0,j-1],
                if(s.charAt(i) == p.charAt(j)) {f[i][j] = f[i-1][j-1]; continue;}
                f[i][j] = Math.min(Math.min(f[i-1][j], f[i][j-1]),f[i-1][j-1]) + 1;
            }
        }
        return f[m][n];
    }
}

状态转移时,要想清楚边界,时时要理解状态的定义

class Solution {
    public int minDistance(String w1, String w2) {
        w1 = " " + w1; 
        w2 = " " + w2;

        int m = w1.length(), n = w2.length();
        int[][] f = new int[m][n];

        for(int i = 1; i < m; i++) f[i][0] = i;
        for(int i = 1; i < n; i++) f[0][i] = i;

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                f[i][j] = Math.min(f[i-1][j], f[i][j-1]) + 1;
                int t = w1.charAt(i) == w2.charAt(j) ? 0 : 1;
                f[i][j] = Math.min(f[i-1][j-1] + t,f[i][j]);
            }
        }

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