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

Question

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

A．贪心

B．分治

C．分支—限界

D．动态规划

Answer 1

正确答案：D
解析：对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，是利用动态规划策略解决的经典问题之一。利用动态规划策略求解该问题时可以通过查表得到已经计算出的子串的最长公共子序列，从而避免重复计算。例如，利用动态规划算法可以得到串1,0,0,1,0,1,0,1＞和0,1,0,1,1,0,1,1＞的最长公共子序列的长度为6，如“101011”。