真题解析

答案:C

考纲知识点:动态规划-序列类DP(LCS)

解析:

状态表示：DP[i][j]:由A序列的前i个字母，且由B序列的前j个字母中构成的LCS的长度。

状态转移方程：

①若Ai和Bj都位于公共子序列中，则必须满足Ai==Bj,也就是A的第i个元素与B的最第j元素相同。那么，只需要找LCS(A[i-1],B[j-1])，结果为LCS(A[i-1],B[j-1])的长度+1。

②若Ai和Bj至少有一个不位于公共子序列中，

1.LCS可以在(a1,a2,.....a[i-1])和(b1,b2,b3.....b[j])中找，记为LCS(A[i-1],B[j])；

2.LCS可以在(a1,a2,.....ai)和(b1,b2,b3.....b[j-i])中找，记为LCS(A[i],B[j-1])；

3.LCS可以在(a1,a2,.....a[i-1])和(b1,b2,b3.....b[j-1])中找，记为LCS(A[i-1],B[j-1])；

第三个一定不优于前两个,当前情况记为:
max( LCS(A[i-1],B[j]) , LCS(A[i],B[j-1]) )。

目标状态:DP[n][m]

本题横线为上方的②情况，答案选C。