动态规划：最长公共子序列

Question

我正在复习在寻找两个等长字符串的最长公共子序列的上下文中讨论动态规划的笔记。有问题的算法输出长度（而不是子字符串）。

所以我有两个字符串，说：

S=ABAZDC，T=BACBAD

最长的公共子序列是ABAD（子字符串不必是相邻的字母）

算法如下，其中LCS[i，j]表示S[1..i]和T[1..j]的最长公共子序列：

if S[i] != T[j] then
    LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
else
    LCS[i, j] = 1 + LCS[i - 1, j - 1]

我的笔记声称你可以填写一个表格，其中每个字符串都沿着一个轴写。比如：

B A C B A D

A 0 1 1 1

B 1 1 2 2 2

一个...

Z

D

C

两个问题：

1） 我们实际上是如何开始填写这个表格的。算法是递归的，但似乎没有提供基本情况（否则我只调用LCS[5，5]）？注释声称你可以用i和j做两个简单的循环，并在恒定时间内填充每个点。。。

2） 我们如何修改算法，使最长的公共子序列是相邻字母的序列？我的想法是，一旦发现S中的下一个字母与t中的下一个字母不匹配，我必须将当前子序列的长度重置为0。但这很棘手，因为我想跟踪到目前为止看到的最长的子序列（我看到的第一个子序列可能是最长的）。所以我可能会有一个额外的参数，longesthusfar，当我们最初调用我们的算法并在随后的调用中更改时，它是0。

有人能让这个更严格一点吗？

谢谢

Answer 1

首先，算法是递归的，但实现总是迭代的。换句话说，我们不会显式地从函数本身调用同一个函数（递归）。

我们使用已经填充的表条目来补偿递归。

比如说，你有两条长度为M的绳子。

然后定义维度（M 1）X（M 1）的表。

for(i = 0 to M)
{
  LCS[0][i]=0;
}
for(i = 1 to M)
{
  LCS[i][0]=0;
}

你得到一张像这样的桌子

    B,A,C,B,A,D
  0,0,0,0,0,0,0
A 0
B 0
A 0
Z 0
D 0
C 0

第0列中的每个零表示，如果不考虑字符串BACBAD的字符，则LCS的长度=0。

第0行中的每个零表示，如果不考虑字符串ABAZDC的任何字符，则LCS的长度=0。

其余条目使用您提到的规则填充。

for(i = 1 to M)
{
 for(j = 1 to M)
 {
  if S[i-1] != T[j-1] then
    LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
  else
    LCS[i, j] = 1 + LCS[i - 1, j - 1]
 }
}

请注意，它的S[i-1]！=T[j-1]而不是S[i]！=T[j]，因为当您填充LCS[i， j]时，您总是比较S的i-1个字符和T的j-1个字符。

LCS的长度由LCS[M，M]给出。

理解这一点的最好方法是手动尝试。

回答你的第二个问题，你不需要修改算法太多。

解决方案位于用于检索LCS的表中。

for(i = 1 to M)
{
 for(j = 1 to M)
 {
  if S[i-1] != T[j-1] then
  {
     LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
     if(LCS[i - 1, j]>=LCS[i, j - 1])          
      T[i-1][j-1]='u'//meaning up
     else T[i-1][j-1]='l'//meaning left
  }
  else
  {
    LCS[i, j] = 1 + LCS[i - 1, j - 1]
    T[i-1][j-1]='d'//meaning diagonally up
  }
 }
}

现在，为了知道两个字母共用的最长子串（相邻字母），对角遍历T。

长度=对角线中发现的最大连续d数。

任何平方矩阵NXN的对角遍历由完成。

包括主对角线的下三角形

j=N-1
while(j>=0)
{
 i=j;k=0;
 while(i <= N-1)
 {
  entry T[i][k];
  ++i;++k
 }
 --j;
}

上部三角形

j=1;
while(j<=N-1)
{
 i=j;k=0;
 while(i<=N-1)
 {
  entry T[k][i];
  ++k;++i;
 }
 --j;
}