我刚刚阅读了论文,我同意证明有点,嗯,简洁。(我想说它缺少一些非常重要的步骤!)
直观地说,证明背后的想法是表明,如果您使用贪婪策略并在游戏结束时从一堆编号为 p 的牌中挑选任何一张牌,您可以在原始数组中找到一个长度为 p 的递增子序列。如果你能证明这个事实,那么你可以得出结论,贪心策略产生的最大堆数是最长递增子序列的长度。
为了正式证明这一点,我们将论证以下两个不变量在每一步都成立:
从左到右阅读时,每堆顶部的卡片按排序顺序排列。
在任何时间点,每一堆中的每张牌都是递增子序列的一部分,其长度由堆索引给出。
第 (1) 部分很容易从贪心策略中看出 - 每个元素都尽可能放在左侧,而不会违反小卡片必须始终放在大卡片顶部的规则。这意味着如果将一张卡片放入堆 p 中,我们实际上是在采用排序序列并将第 p 个元素的值减少到大于位置 p - 1 中的任何值(如果存在)的值。
要查看第 (2) 部分,我们将进行归纳。第一张放置的卡片被放入堆 1,它也是长度为 1 的递增子序列的一部分(卡片本身)。对于归纳步骤,假设在放置 n 张卡片后该属性成立并考虑第 (n+1) 个。假设它最终在堆 p 中。如果 p = 1,那么这个主张仍然成立,因为这张牌本身就形成了一个长度为 1 的递增子序列。否则,p > 1。现在,看看堆顶上的牌 p - 1。我们知道这张牌的价值小于我们刚刚放置的牌的价值,否则我们会将牌放在上面桩。我们还知道,那堆牌顶部的牌在我们刚刚按原始顺序放置的牌之前,因为我们是按顺序打牌的。通过我们现有的不变量,