问题
单项选择题
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用 (57) 策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串<1,0,0,1,0,1,0,1,>和<0,1,0,1,1,0,1,1,>的最长公共子序列的长度为 (58) 。
(57)处填()。
A.分治
B.贪心
C.动态规划
D.分支一限界
答案
参考答案:C
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用 (57) 策略可以有效地避免子串最长公共子序列的重复计算,得到时间复杂度为O(n2)的正确算法。串<1,0,0,1,0,1,0,1,>和<0,1,0,1,1,0,1,1,>的最长公共子序列的长度为 (58) 。
(57)处填()。
A.分治
B.贪心
C.动态规划
D.分支一限界
参考答案:C