如何解决间隙条件下的LCS（最长公共子序列）

Question

我知道一般的LCS问题和算法。

是这样的：

LCS(Xi, Yj) = [0 (i = 0 or j = 0) 
      or LCS(Xi-1, Yj-1) + 1 (xi = yj) 
      or max(LCS(Xi, Yj-1), LCS(Xi-1, Yj)) (xi != yj)] 

但是，如果我们添加一个间隙条件？

例如：

String A is cttauaucagu 
String B is cautauatcgu 

if no gap condition 
lcs = cauauagu 

if gap = 1 (lcs gap is under 1) 
lcs = auaua 

if gap = 0 (lcs gap is under 0) 
lcs = taua 

可视化表示：

如何解决这个问题？

如何制作DP表格？

Answer 1

这种情况下的解决方案没有多大区别。您将不得不向dp添加另外两个参数 - 这是来自两个字符串的公共子序列中包含的最后一个元素的索引。然后，在dp的每一步中，只搜索给定字符串中的_last_included_element和the_last_included_elemement + gap + 1之间的相等元素。