对公共子序列进行最少的编辑

Question

给出这个问题的表述和代码块中的官方解决方案：

给定一个包含 n 个整数 A 的数组和一个包含 m 个整数 B 的数组，使得

n <= m

。为了使 A 成为 B 的子序列，您需要用其他整数替换 B 的元素的最小数量是多少？ （不一定在连续索引上）

例如，对于

A = [1, 5, 2, 3]

和

B = [1, 4, 2, 5, 6, 2, 5]

，答案是 1，将 B 的最后一个元素替换为 3。同样，对于

A = [1, 5, 2, 3]

和

B = [5, 8, 8, 2, 8, 8, 3]

，答案是 2，它将 B 的前两个元素替换为 1 和 5 得到。 您的解决方案需要在

O(n*m)

时间内运行。

public static int editToSubsequence(int n, int m, int[] A, int[] B) {
    // IDEA: Dynamic programming DP[i][j] = minimum number of edits such that
    // indices 0...i-1 of A are a subsequence of indices 0...j-1 of B.
    // We set DP[i][j] = n + 1 for j < i, because that case is impossible.
    // Otherwise, the main recursion is:
    //   - if A[i - 1] = B[j - 1], we can set DP[i][j] = DP[i - 1][j - 1]
    //   - else, we can set DP[i][j] = DP[i - 1][j - 1] if we edit B[j],
    //    or DP[i][j] = DP[i][j - 1] if we do not use B[j]
    
    int[][] DP = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < i; j++) {
        DP[i][j] = n + 1;
      }
    }
    
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= m; j++) {
        if (A[i - 1] == B[j - 1]) {
          DP[i][j] = DP[i - 1][j - 1];
        } else {
          DP[i][j] = Math.min(DP[i][j - 1], DP[i - 1][j - 1] + 1);
        }
      }
    }
    
    return DP[n][m];
  }

有人可以解释这种方法的直觉应该来自哪里吗？我熟悉 DP 中的最长公共子序列和最小编辑距离，但这对我来说不是一个明显的方法。

Answer 1

为了真正理解 DP 解决方案，我会首先查看朴素的递归解决方案，这有助于理解方法/主要思想。

让我们看看 A 和 B 的最后一个整数以及最优解的可能性。

如果整数相同，则意味着 A 和 B 的解将与 A 和 B 相同，但不包含两者的最后一个整数，因为您可以使用 B 中的最后一个整数作为 A 中的最后一个整数子序列（无论你真的使用它还是使用另一个可以使用的都没关系）。

如果它们不相同，您有 2 个选择：

1. 根本不要使用 B 最后一个整数，这意味着解是没有最后一个整数的 B 和整个 A。

2. 您确实使用了它，但您更改了它，这意味着您再次使用 A 和 B，但没有两者的最后一个整数，但加上 1 更改导致您必须将 B 最后一个整数更改为 A 最后一个整数。

关于您的停止条件，您还有 2 个选择：

1. 如果 A 长度大于 B，则没有可能的解决方案（将其定义为无限变化）

2. 如果 A 没有整数意味着您不需要更改任何内容，并且 B 可以是任何大小（将其定义为 0 更改）

因为在我们的停止条件下 B 必须大于 A