0011 算法笔记：DP-LCS

问题描述：给定一个原始数据集D={d1,d2,…,dn}及其对应的标签集合L={l1,l2,…,lm}（其中n≥m），假设存在某个分类器C能够将D映射到L中相应的标签上，则分类器C即为数据集D上的一个学习器。这种基于实例的学习方法被称为基于示例的学习（learning by example）。例如，在图像分类任务中，“学习者”可能通过观察多张狗的照片来学习如何识别狗这个类别。

** 问题解析** ：在问题分析部分中设定两个集合X和Y分别为{A,B,C,B,D,A,B}与{B,D,C,A,B,A}。求解这两个集合的最大公约数中最长的那个连续排列即为我们要求的目标值。最直观的方法即是穷举法。对于集合X中的每一个可能子序列（subsequence），逐一验证其是否同时也是集合Y中的一个连续排列（subsequence）。根据集合论的基本原理可知：包含m个元素的集合共有2^m个不同的子集。因此采用穷举法的时间复杂度呈指数级增长（exponential growth）。进一步分析该问题特征可知：最长公共子序列问题实际上具有明显的最优子结构特性（optimal substructure property）。

设序列X={x1,x2,……xm}和Y={y1,y2,……yn}的最长公共子序列为Z={z1,z2,……zk}。则有：

(1)若xm=yn,则zk=xm=yn,且zk-1