一句话总结：看起来复杂，动规分析以后就比较简单。

原题链接：583 两个字符串的删除操作

本质就是求两个字符串的最短子序列的长度。已经做过，不再详解。

class Solution {
    public int minDistance(String word1, String word2) {
        // dp数组找最长相同子序列长度，然后两字符串总长减去2 * 最长长度即可
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return m + n - dp[m][n] * 2;
    }
}

 原题链接：72 编辑距离

看起来比较难，用动规五部曲分析一下：

1. 确定动规数组及其下标的含义： dp[i][j]表示以i - 1结尾的word1的子串到以j - 1结尾的word2的子串的最近的编辑距离；
2. 确定状态转移方程：分为两种情况，当word1[i - 1] == word2[j - 1]时，显而易见的dp[i][j] = dp[i - 1][j - 1]；当word1[i - 1] != word2[j - 1]时，最短的编辑距离又分为三种情况，首先是从删除word1[i - 1]，此时dp[i][j] = dp[i - 1][j] + 1；然后是删除word2[j - 1]，此时dp[i][j] = dp[i][j - 1] + 1；最后一种情况则是将word1[i - 1]替换为word2[j - 1]以使得两者相等，那么就有dp[i][j] = dp[i - 1][j - 1] + 1；在这三种情况中取最小值即可。即if (word1.charAt(i  -1) != word2.charAt(j - 1)) dp[i][j] = Math.min(Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1), dp[i - 1][j - 1] + 1)；
3. dp数组的初始化：对于任意dp[i][0]，编辑距离一定是删除完所有字符，因此dp[i][0] = i；同理dp[0][j] = j；
4. dp数组的遍历顺序：从上面的递推方程可见依赖于i - 1和j - 1，因此从前往后即可；
5. 举例推导：略。

最终代码如下：

class Solution {
    public int minDistance(String word1, String word2) {
        char[] cs1 = word1.toCharArray(), cs2 = word2.toCharArray();
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (cs1[i - 1] == cs2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1));
            }
        }
        return dp[m][n];
    }
}