如何解決間隙條件下的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之間的相等元素。