dynamic-programming - 动态规划

Question

谁能向我解释最长公共子序列问题的解决方案？具体来说，递归关系是

if(x _i =y _j ) 那么答案= max _L (i-1, j-1) +1

else answer=Max{Max _L (i-1, j), Max _L (i, j-1)}

x _i / y _i是构造表中的字母。Max _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") 存储在 Table[i-1,j -1] 中（即 max _L [i-1][j-1]）