3

关于最长公共子序列问题，所有在线资源中介绍的基本算法对我来说都很清楚。此处描述了此算法：

在此处输入图像描述

我不清楚的是为算法的动态编程版本提出的算法，它无处不在，如下所示： 

function LCSLength(X[1..m], Y[1..n])  
    C = array(0..m, 0..n)  
    for i := 0..m  
       C[i,0] = 0  
    for j := 0..n  
       C[0,j] = 0  
    for i := 1..m  
        for j := 1..n  
            if X[i] = Y[j]  
                C[i,j] := C[i-1,j-1] + 1  //Here shouldn't we change i?
            else  
                C[i,j] := max(C[i,j-1], C[i-1,j])  
    return C[m,n]

但是我看不出DP版本是如何等效的。令我困扰的是，在 DP 版本中，当我们X[i] == Y[j]在内循环中发现时，我们继续计算 DP 相同i；即内部循环的其余部分保持与相同的比较X[i]。既然递归算法说我们应该评估 C[i - 1, j - 1]，我们不应该继续下一个i吗？

4

2 回答 2

5

动态规划背后的想法是反向评估递归函数，从基本情况开始，迭代地为越来越大的子问题建立答案，直到为整个输入问题计算出答案。

如果您正在递归地评估此函数，那么在您提到的情况下，您绝对会通过递减 i 和 j 来递归。但是，在动态编程版本中，您不是从 LCS[i, j] 开始并尝试通过评估 LCS[i-1, j-1] 来评估它。您从 LCS[i-1, j-1] 开始并使用它来评估 LCS[i, j]。

具体来说，这段代码所做的是首先通过直接使用基本案例解决方案为所有 i 和 j 计算 LCS[i, 0] 和 LCS[0, j]。接下来，它使用所有 j 都知道 LCS[0, j] 的事实来计算所有 j 的 LCS[1, j]。然后它使用所有 j 都知道 LCS[1, j] 的事实来计算所有 j 的 LCS[2, j]，依此类推。

结果，是时候计算 LCS[i, j] 并且您的特定情况适用，该算法不需要递减 i 或 j 并递归地向下下降。它已经计算了 LCS[i-1, j-1]，因此它可以读取该值并继续构建表中的其余值。

视觉上最容易看到这一点。假设您要查找字符串“canon”和“annie”的 LCS。我们从这个 2D 表开始：

    A N N I E
  . . . . . .
C . . . . . .
A . . . . . .
N . . . . . .
O . . . . . .
N . . . . . .

最初，我们为所有 i 和 j 设置 LCS[0, j] = LCS[i, 0] = 0：

    A N N I E
  0 0 0 0 0 0
C 0 . . . . .
A 0 . . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

现在，我们将逐行浏览此表，并使用原始问题中描述的重复来填写缺失的条目。遍历第一行时，我们将比较字母 C 和单词“ANNIE”中的所有字母。我们永远找不到匹配项，所以我们总是使用递归 LCS[i, j] = max(LCS[i - 1, j] + LCS[i, j - 1])。这总是评估为零，所以我们得到这个：

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 . . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

这是有道理的，因为该表的第一行表示字符串 C 的 LCS 的长度以及 ANNIE 的所有前缀。

在下一行中，我们将尝试查找字符串 CA 的 LCS 和 ANNIE 的所有后缀。我们考虑的第一个条目匹配 A 和 A。由于这是一个匹配，我们使用递归 LCS[i, j] = 1 + LCS[i - 1, j - 1]，其计算结果为 1：

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

同样，我们可以通过注意“CA”和“A”的 LCS 是长度为 1 的序列 A 来检查这一点。

这里重要的细节是我们在这里不递减 i 或 j。 我们仍然需要填写这一行的其余部分，因此我们将继续前进。

对于这一行的其余条目，我们将 A 与 ANNIE 的每个字符进行比较，发现它不匹配。因此，我们将使用递归 LCS[i, j] = max(LCS[i-1, j], LCS[i, j-1])，它总是通过从其余部分中提取 1 来评估为 1行的。这显示在这里：

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

继续下一行为我们提供了以下信息：

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 1 2 2 2 2
O 0 . . . . .
N 0 . . . . .

同样，这是有道理的。“CAN”和“A”的LCS就是“A”，“CAN”和“AN”的LCS就是“AN”等等。

我们可以通过表的其余部分重复此操作以找到此结果表：

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 1 2 2 2 2
O 0 1 2 2 2 2
N 0 1 2 3 3 3

我们知道 LCS 的长度为 3，这是正确的。

希望这可以帮助！

于 2012-12-26T20:12:31.057 回答
1

C[i][j] 的值仅取决于 C[i][j-1]、C[i-1][j] 和 C[i-1][j-1]。因此，当我们在内循环中得到 C[i][j] 的值时，我们可以继续计算 C[i][j+1]，因为 C[i][j] 和 C[i-1][ j+1] 和 C[i-1][j] 都已经计算过了。

于 2012-12-26T20:13:35.133 回答