【摘要】 文章分析了LCS问题的最优子结构性质,建立了求最优值的递归关系式。在此基础上,进一步分析、总结、归纳,指出了LCS的长度具有的性质及相关定理。设计了一种高效LCS算法,与现有算法相比,该算法空间复杂度非常低、时间复杂度较低。更多还原

【Abstract】 This paper analyzes nature of optimal substructure for the LCS problem,and establishes the recursion formula to get the optimal value. Through further analysis,many natures and theorems for the LCS problem are summarized and a high-efficient algorithm of LCS is designed in this paper. It’s space and time complexities are lower than the existing algorithms.更多还原