第 7 题 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 X={x_1,x_2,x_3,\cdots,x_m}X=x1​,x2​,x3​,⋯,xm​ 和 Y={y_1,y

第 7 题YJG100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 X={x_1,x_2,x_3,\cdots,x_m}X=x1​,x2​,x3​,⋯,xm​ 和 Y={y_1,y_2,y_3,\cdots,y_n}Y=y1​,y2​,y3​,⋯,yn​，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 Z={z_1,z_2,z_3,\cdots,z_k}Z=z1​,z2​,z3​,⋯,zk​, 使得序列 ZZ 既是序列 XX 的子序列，又是序列 YY 的子序列，且序列 ZZ 的长度 kk 在满足上述条件的序列里是最大的。 （注：序列 AA 是序列 BB 的子序列，当且仅当在保持序列 BB 元素顺序的情况下，从序列 BB 中删除若干个元素，可以使得剩余的元素构成序列 AA。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）YJG100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 A. 44YJG100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 B. 55YJG100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 C. 66YJG100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 D. 77YJG100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库