动态规划

• 一个样本作行一个样本作列对应模型, 讨论结尾

• dp数组的含义：
  • str1拿出前i个前缀字符串和str2拿出前j个前缀字符串，最小编辑距离是多少？
• 首先把第一行和第一列给填好
• 然后填其他普遍情况的行和列

• 1. 保留 i-1
     • ① 当 i-1 位置字符 ≠ j - 1位置字符时，[ i -1] 位置字符 替换成[ j - 1]位置字符 ，所以就是dp[i - 1][j -1] + 一个替换操作
     • ② 当 i-1 位置字符 ＝ j - 1位置字符时，dp[i - 1][j - 1] + 0
       • 所以可能性①和可能性②是互斥的
     • ③先让我的整体变成目标的前缀，然后再加一个字符

• 1. 不保留 i-1
     • ①先让我的前缀变成目标的整体，然后再删除最后一个字符

 public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null ) {
            return 0;
        }
        char[] str1 = word1.toCharArray();
        char[] str2 = word2.toCharArray();
        int N = str1.length;
        int M = str2.length;
        // 有一个字符串为空串
        if (N * M == 0) {
            return N + M;
        }
        // dp[i][j]: str1拿出前i个前缀字符串和str2拿出前j个前缀字符串，最小编辑距离是多少？
        int[][] dp = new int[N + 1][M + 1];
        // dp[0][0] = 0
        for (int i = 1; i <= N; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <=M; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 保留 i - 1位置的字符
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                // 不保留 i - 1位置的字符
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
            }
        }
        return dp[N][M];
    }