为什么这个最长公共子序列的DP解决方案能够正常工作？

Question

关于最常见的子序列问题,所有在线资源中提供的基本算法对我来说都很清楚.此算法在此处描述:

我不清楚的是为算法的动态编程版本提供的算法,无处不在如下:

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吗？

Answer 1

动态编程背后的想法是反向评估递归函数,从基本情况开始,迭代地为更大和更大的子问题建立答案,直到为整个输入问题计算答案.

如果你以递归的方式评估这个函数,那么在你提到的减去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].接下来,它使用LCS [0,j]已知所有j来为所有j计算LCS [1,j]的事实.然后它使用LCS [1,j]为所有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是序列A(长度为1)来检查这一点.

这里重要的细节是我们不会在这里减少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,这是正确的.

希望这可以帮助!