对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,(2006年上半年软件设计师上午综合知识真题解析)
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(1)策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1>的最长公共子序列的长度为(2)。
(1)A、分治
B、贪心
C、动态规划
D、分支—限界
(2)A、3
B、4
C、5
D、6
参考答案: C、D
参考解析:正在整理中,欢迎在文下评论区提供答案解析,谢谢!