对于求取两个长度为n的字符串的最长公共子序列(LCS)问题,利用(57)策略可以有效地避免子串最长公

Question

对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用(57)策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n2)的正确算法。串＜1，0，0，1，0，1，0，1，＞和＜0，1，0，1，1，0，1，1，＞的最长公共子序列的长度为(58)。

A．分治

B．贪心

C．动态规划

D．分支一限界

Answer 1

正确答案：C
解析：本题考查的是动态规划算法策略的典型应用。LCS问题是利用动态规划策略解决的经典问题之一，利用动态规划求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。利用动态规划算法可以得到题目中两个串的最长公共子序列长度为6，如“101011”。