经典动态规划：编辑距离

72. 编辑距离

进入今天内容之前，可以先阅读 动态规划解题套路框架 和 动态规划设计：最长递增子序列 回顾一下动态规划问题的解题框架和套路

问题分析

详情可见题目 编辑距离

对于样例s1="horse", s2="ros"，我们来手动模拟一下过程

前提：我们固定s2不变，对s1进行操作，使s1 = s2停止；同时我们从后往前开始分析

1. 首先看一下初始状态，如下图 1 所示；
2. 此时我们要处理的字符为[e, s]，执行的操作是删除字符e，i向前移动一位，现在状态如下图 2 所示；
3. 此时我们要处理的字符为[s, s]，不执行任何操作，i, j均向前移动一位，现在状态如下图 3 所示；
4. 此时我们要处理的字符为[r, o]，执行的操作是删除字符r，i向前移动一位，现在状态如下图 4 所示；
5. 此时我们要处理的字符为[o, o]，不执行任何操作，i, j均向前移动一位，现在状态如下图 5 所示；
6. 此时我们要处理的字符为[h, r]，执行的操作是替换字符：h -> r，i, j均向前移动一位，现在状态如下图 6 所示；

好了，到现在为止，整个模拟过程结束。我们执行了 3 次操作！！现在如果把上述过程交给计算机去处理，又应该如何进行呢？？

我们可以人为的决策出最优的操作，但是计算机不可以。它不知道每一次该如何选择删除, 插入 or 替换

计算机虽然笨，但是它快呀！我们可以让计算机暴力穷举所有的选择，即：每一次进行选择的时候，把上述三种选择都执行一遍，然后选择出最优解！！

结合框架分析

对于这个问题，我们先明确一下「原问题」和「子问题」分别是什么？

「原问题」：s1[0..m]和s2[0..n]的编辑距离

「子问题」：s1[0..i]和s2[0..j]的编辑距离，其中0 <= i < m and 0 <= j < n

回顾一下动态规划的框架：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

• 明确 base case：显然是当i = -1 or j = -1时

  • 当s1已经走到尽头，此时应该返回s2剩下的长度j + 1。原因：直接在s1的左边插入j + 1个s2剩下的元素即可
  • 当s2已经走到尽头，此时应该返回s1剩下的长度i + 1。原因：直接在s2的左边插入i + 1个s1剩下的元素即可

• 明确「状态」：原问题和子问题中会发生变化的变量。s1[0..i]和s2[0..j]字符串的会不断地向 base case 靠近，所以唯一的「状态」就是字符串s1[0..i]和s2[0..j]

• 明确「选择」：导致「状态」产生变化的行为。字符串s1[0..i]和s2[0..j]为什么变化呢？因为在选择不同的操作，每选择一种操作，字符串就会对应的收缩。所以说「删除 or 插入 or 替换」就是「选择」(每次都可在选择任意一种操作)

• 明确 dp 数组/函数的定义：这里采用自顶向下的解法，所以会有一个递归的dp函数，一般来说函数的参数就是状态转移中会变化的量，即：「状态」；函数的返回值就是s1[0..i]和s2[0..j]的编辑距离

递归暴力实现

根据上面的分析，我么可以写出第一版暴力的递归版本代码，如下：

x
public int minDistance(String word1, String word2) {
    return dp(word1, word1.length() - 1, word2, word2.length() - 1);
}
// 从后往前递归
// dp 定义：计算 word1[0..i] 和 word2[0..j] 的编辑距离
private int dp(String word1, int i, String word2, int j) {
    // base case
    if (i == -1) return j + 1;
    if (j == -1) return i + 1;
    
    // 当前元素相等的情况
    if (word1.charAt(i) == word2.charAt(j)) return dp(word1, i - 1, word2, j - 1);
    // 当前元素不等的情况
    else {
        return min(
            dp(word1, i, word2, j - 1),         // 插入
            dp(word1, i - 1, word2, j),         // 删除
            dp(word1, i - 1, word2, j - 1)      // 替换
        ) + 1;
    }
}
// 求三个数中的最小值
private int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

此版本没有任何的优化，纯递归暴力！！

「递归+备忘录」实现

其实我们优化也是从「重叠子问题」入手！首先判断是否存在「重叠子问题」，然后再用一个「备忘录」记录子问题的结果

这里介绍一种判断是否存在「重叠子问题」的小技巧

我们把上面的dp()函数简化一下，只抽出核心部分分析。简化版本如下所示：

xxxxxxxxxx
int dp(int i, int j) {
    return min(
        dp(i, j - 1),     // 插入
        dp(i - 1, j),     // 删除
        dp(i - 1, j - 1)  // 替换
    ) + 1;
}

现在画出执行时的部分递归树：

可以很明显的看到存在「重叠子问题」

所以优化思路也很容易给出：

x
// 备忘录
private int[][] emeo;
public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    emeo = new int[n1][n2];
    return dp(word1, n1 - 1, word2, n2 - 1);
}
// 从后往前递归
// dp 定义：计算 word1[0..i] 和 word2[0..j] 的编辑距离
private int dp(String word1, int i, String word2, int j) {
    // base case
    if (i == -1) return j + 1;
    if (j == -1) return i + 1;

    if (emeo[i][j] != 0) return emeo[i][j];

    if (word1.charAt(i) == word2.charAt(j)) emeo[i][j] = dp(word1, i - 1, word2, j - 1);
    else {
        emeo[i][j] = min(
            dp(word1, i, word2, j - 1),     // 插入
            dp(word1, i - 1, word2, j),     // 删除
            dp(word1, i - 1, word2, j - 1)  // 替换
        ) + 1;
    }
    return emeo[i][j];
}
private int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

「递推」实现

上面的「递归」方法是自顶向下，下面介绍「递推」自底向上的方法

「递归」核心是dp()函数，参数为状态，返回值为子问题的最优解

「递推」核心是dp[]数组，下标为状态，数组值为子问题的最优解

显然这个问题我们需要用到二维dp[][]数组，即dp[i][j]表示s1[0..i]和s2[0..j]的编辑距离

确定 base case

同时我们还需要明确 base case 是什么？这个和「递归」中的 base case 有些许区别！！

首先我们将dp[][]和字符串的对应关系整体偏移一位，什么意思呢？直接看图：

可以看到 base case 即为第一行和第一列的值，至于为什么？我们可以这样理解！！

• 先看dp[0][0]，即s1 = ""和s2 = ""的编辑距离，即两个空字符串的编辑距离为 0
• 在看dp[0][1]，即s1 = ""和s2 = "r"的编辑距离，我们只需要在s1中插入字符r即可，操作为 1 次，即编辑距离为 0
• dp[0][2]、dp[0][3]同理
• dp[1][0]、dp[2][0]、dp[3][0]、dp[4][0]、dp[5][0]也同理

所以就很好理解了为什么该方法中的 base case 是这个样子了

确定遍历方向

现在又出现了另外一个问题，怎么遍历来填满dp[][]

注意看黄色区域，当s1[i] = s2[j]时，直接dp[i][j] = dp[i - 1][j - 1]

所以根据「当前状态是根据哪些之前状态转换而来」可以确定遍历的顺序，代码如下所示：

x
for (int i = 1; i < dp.length; i++) {
    for (int j = 1; j < dp[0].length; j++) {
        // 相等情况
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
        else {
            // 不等情况
            dp[i][j] = min(
                dp[i][j - 1],
                dp[i - 1][j],
                dp[i - 1][j - 1]
            ) + 1;
        }
    }
}

所以最终代码也可以写出：

x
public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    // dp[i][j] : word1[0..i-1] 和 word2[0..j-1] 的编辑距离
    int[][] dp = new int[n1 + 1][n2 + 1];
    // base case
    for (int i = 0; i < dp.length; i++) dp[i][0] = i;
    for (int j = 0; j < dp[0].length; j++) dp[0][j] = j;

    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
            else {
                dp[i][j] = min(
                    dp[i][j - 1],
                    dp[i - 1][j],
                    dp[i - 1][j - 1]
                ) + 1;
            }
        }
    }
    return dp[n1][n2];
}
private int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}