动态规划

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]）