一个LCS小定理的证明过程

几年前写的，今天翻出来，看来当年还挺爱专研的，哈哈。

Longest Common Subsequence

序列S = {5, 3, 4, 9, 6, 2, 1, 8, 7}

则{3, 4, 6}是S的一个严格递增子序列(Strictly Increasing Subsequence)

Cover: {(5, 3, 2, 1), (4), (9, 6), (8, 7)}是其一个覆盖集合，覆盖集合必须包含序列的所有元素，并且集合中的每个子序列都必须是非递增的。

 定理：

     若IS是序列S的一个严格递增子序列，C是序列S的一个覆盖集合，且|IS| = |C|，则IS为序列S的最长严格递增子序列(LIS)，|C|是序列S的最小覆盖集。

证明：     

     若IS1, C1是序列S的一个严格递增子序列和覆盖集，由于C1中的每个子序列都是非递增的，所以IS1最多包含每个子序列中的一个元素，所以|IS1| <= |C1|.也就是说严格递增字序列的长度一定不超过任何覆盖集合的大小（最长严格字序列的长度不会超过最小覆盖集合的大小）。

     由于|IS| = |C| >= 任何一个严格递增子序列, 所以IS是最长严格递增子序列。

     下面证明C是最小覆盖集合

     假设存在C1使得|C1| < |C|，由于|IS|=|C|，那么IS肯定会包含C1中某个子集的两个元素，这必然违反了IS的严格递增原理，所以假设不成立，所以C是最小覆盖集合。

     证毕