已知序列X=＜A,B,C,B,D,A,B＞,Y=＜B,D,C,A,B,A＞，则序列X和Y的最长公共子序列是（ ）
A: ＜B,C,B,A＞
B: ＜B,D,A,B＞
C: ＜B,D,B,A＞
D: ＜B,C,A＞
A: ＜B,C,B,A＞
B: ＜B,D,A,B＞
C: ＜B,D,B,A＞
D: ＜B,C,A＞
举一反三
- 【填空题】若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列_____________________________
- 给定2个序列X={x1,x2,...,xm}和Y={y1,y2,...,yn},找出X和Y的最长公共子序列。使用穷举法时,对X的所有子列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列。那么Y有多少个不同子序列 A: m B: 2 C: n D: 2
- 已知序列X={x1,x2,…,xm},序列Y={y1,y2,…,yn},使用动态规划算法求解序列X和Y的最长公共子序列,其最坏时间复杂度为(<br/>)。 A: O(m * n) B: O(m + n) C: O(m<br/>* 2n) D: O(n<br/>* 2m)
- 用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程
- 使用动态规划算法求解最长公共子序列问题，引入数组c[i][j]存储序列x[1..i]和y[1..j]的最长公共子序列的长度，则对于长度为m和n的两条序列，其最长公共子序列的长度为c[m][n]。