Skip to content

Tag Archives: LIS

我为何中止DP系列文章的写作

前几天,在写作《动态规划中的线形模型》时,写到了讨论LIS问题的章节。顿悟一般,理解了LIS的数学本质。原来LIS问题就是这样一个问题: 一个有限集S,其中定义了两个全序关系<1和<2,用这两个全序关系定义一个偏序关系<:x<y当且仅当x<1y且x<2y。求偏序集(S,<)的最长链。 没错,这就是LIS问题的数学本质。知道了这个以后就可得出很多关于LIS及相关问题的结论。由于本篇文章并非教程,对这些结论不详加解释。 在原本的LIS问题中,第一个全序关系是“序列中x在y的前面”,第二个全序关系是“x小于y”。如果我们按照第二个全序关系对序列进行排序,可以得到原问题的一个对偶问题。即:对原序列进行排序,再把排序后序列的每个元素换成在原序列中的下标。两个对偶问题的答案是一样的,也就是说原序列中的LIS长度,肯定等于得到的新序列中的LIS长度。而对偶问题有一个非常好的性质:它的序列中的所有元素都在1..N中取值。这就带来了很多很多种O(NlogN)算法的思路,比如说可以用virtual binary tree。 既然LIS的本质是要求“偏序集的最长链”,那么就可以应用组合数学中有关的定理。例如熟悉的定理:最长链的长度等于反链的划分数;以及其对偶定 理:最长反链的长度等于链的划分数。所以LIS中那个让很多人不理解的结论就昭然若揭了。为何上升子序列的覆盖数等于最长不上升子序列的长度?因为上升子序列是链,不上升子序列是反链。 所有可以转化为LIS问题求解的OI题目一定满足LIS的数学本质。也就是说,需要用LIS的算法解决的题目,一定能找到两个全序关系,和由它们定义的偏序关系。例如那道经典的给定一些矩形造一座塔的问题,为什么按照矩形的长排序然后求宽的LIS。原因很简单,两个全序关系就是由矩形的长和宽定义的,而LIS就是要先按照其中一个全序关系排序以得到序列。 可以对LIS的数学本质进行扩展,也就是对LIS问题进行扩展,例如<1和<2不一定都得是全序关系,可以有一个是偏序关系,这个偏序关系也可能是另外两个全序关系定义的,等等……这样又可以解决更多题目,例如“三维导弹拦截”。 …… LIS问题其实只是线型动态规划中非常简单的一个模型,通过思考它的数学本质,竟然就可以得到如此多的结论,由这些结论就可以编制出无穷无尽的OI题……这让我欣喜异常。 然而,LIS的数学本质中涉及到的离散数学中的概念:全序、偏序、链,这都是我还非常非常陌生的概念。连这些概念都不敢说懂,我怎么敢说我懂了LIS问题?我怎么敢写出一份涉及它的教程? 是的,通过深入的思考,我充分理解到:动态规划的每一个模型,都可能有着深不见底的数学本质;不掌握足够多的数学工具,就不可能从本质上把握动态规划。 可我掌握的数学太少了,特别是用处特别大的离散数学,只是浅尝辄止。我深感现在的能力无法写出一份好的动态规划总结。更让我恐慌的是:竟然有那么多人,会那么仔细地,甚至带着崇拜的眼光,阅读我的总结。 由于数学能力不足,也为了避免误人子弟,我已经中止了DP系列文章的写作。今天发布的《背包问题九讲v1.1》是今年的最后一次发布。 我对期待着《动态规划中的线形模型》的所有人表示无比愧疚的歉意。你们高看了我,我目前的能力不足以从本质上把握诸多线形模型,更不足以写出好的总结。对不起,让你们失望了。 但是,要注意我说的是“中止”而非“终止”。那个雄心勃勃的计划没有夭折,只是暂时停顿了。在将来的某一天,在我自认为数学能力足够的时候,也许是在我加入某个ACM-ICPC队伍的时候,我会继续未完成的计划。动态规划的领域是如此迷人,哪怕需要再长的时间,我会将这个写作计划完成。 最后,再次向所有失望的人表示真诚的歉意。