最长公共子序列(C)

问题： 假设集合X包含m个元素，集合Y包含n个元素，试确定X与Y之间的最长公共子序列。

注意：若采用暴力算法进行求解，其时间复杂度将呈现指数级增长，实际应用中并不理想。

进一步分析子问题之间的关联性（假设Z为X与Y的最长公共子序列，其包含k个元素）：

• 若X的最后一个元素与Y的最后一个元素相等，则Z去掉最后一个元素后（即k-1个元素）应为X去掉最后一个元素后的集合（即m-1个元素）与Y去掉最后一个元素后的集合（即n-1个元素）之间的最长公共子序列。
• 若X的最后一个元素不等于Y的最后一个元素，则Z可能是由X去掉最后一个元素后的集合（即m-1个元素）与Y之间的最长公共子序列所构成。
• 若X的最后一个元素不等于Y的最后一个元素，则Z也可能是由X与Y去掉最后一个元素后的集合（即n-1个元素）之间的最长公共子序列所构成。

综上所述：该问题具备最优子结构性质以及子问题重叠特性 ，因此可以采用动态规划方法 进行求解。

关于最长公共子序列的长度 的递推关系式（设m = i；n = j；）：

![在这里插入图片描述](https