動態規劃

Question

任何人都可以向我解釋最長的常見子序列問題的解決方案嗎？具體而言，遞推關係是

如果（X _我 = Y _Ĵ），然後回答= MAX _大號第（i-1，J-1）+1

別的答案=最大{最大_大號第（i-1，j）的最大_大號（I，J-1）}

X _我/Y _我是在構建的表的字母。最大 _L對應於表中的條目構建。

我的問題是爲什麼答案maxL（i-1，j-1）+ 1？爲什麼只有當字母匹配時，我們才需要從左上角對角線添加？ 謝謝

Answer 1

（xi = yj）表示這兩個字符串在它們各自的當前位置上有相同的字符。

讓作爲簡單的例子：

考慮輸入字符串AGGTAB和GXTXAYB。

最後的字符'B'匹配這兩個字符串。[這就是xi == yj條件成立]。

因此LCS長度可以寫成：

LCS("AGGTAB", "GXTXAYB") = 1 + LCS("AGGTA", "GXTXAY") 

LCS（ 「AGGTA」， 「GXTXAY」）被存儲在表[I-1，J-1]（即最大_大號。 [i-1] [j-1]）