private int minDistance_dp(String word1, String word2) {
        if (word1.equals(word2)) {
            return 0;
        }
        int M = word1.length(), N = word2.length();
        if (M == 0 || N == 0) {
            return Math.abs(M - N);
        }

        // init P
        int[][] P = new int[M + 1][N + 1];
        P[0][0] = 0;
        for (int i = 1; i <= M; i++) {
            P[i][0] = i;
        }
        for (int i = 1; i <= N; i++) {
            P[0][i] = i;
        }

        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    P[i][j] = P[i - 1][j - 1];
                } else {
                    P[i][j] = Math.min(P[i - 1][j - 1], Math.min(P[i - 1][j], P[i][j - 1])) + 1;
                }
            }
        }
        return P[M][N];
    }