单选题 适中
#22231

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x 1 ,x 2 ,x 3 ,…,x m }和Y={y 1 ,y 2 ,y 3 ,…

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x1,x2,x3,…,xm}和Y={y1,y2,y3,…yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z1,Z2,Z3,…,Zk},使得序列Z既是序列X的子序列,又是序列Y的子序列,且序列Z的长度k在满足上述条件的序列里是最大的。(注:序列A是序列B的子序列,当且仅当在保持序列B元素顺序的情况下,从序列B中删除若干个元素,可以使得剩余的元素构成序列A。)则序列“ABCAAAABA”和"ABABCBABA"的最长公共子序列长度为(  )

未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析

可以使用经典的动态规划算法,可以看出最长公共子序列是“ABAABA”。