算法奇论——LIS 与打牌有关？看 LIS 的二分搜索解法

CleanIce

2024-07-13 22:12:27

Algo. & Theory

《算法奇论》的第一篇文章啦~~

《算法奇论》是作者开创的新的一个专栏，专门收录各种有关于计算机算法学的奇闻异事，欢迎阅读。

由于本人仅 14 岁，知识、经验可能不足，再加上本文进度比较赶，本文可能有勘误或错别字、拼写错误，还请发现者在评论区指出，作者一定在看到评论后第一时间更正，谢谢！

同篇文章的其他位置：

  1. 知乎：https://zhuanlan.zhihu.com/p/708679644

背景知识

LIS 是一个十分经典的有关子序列的动态规划题目，想必学过动态规划的读者已经非常熟悉这个套路了。这里我们快速复习一下 LIS：

LIS（Longest Increasing Subsequence），最长递增子序列，是指在一个序列中，找出最长的严格递增子序列，并通常需要求其长度。子序列是指由某一序列的元素不可复选重新按照在原序列中的顺序排列而成的一个新序列。

注意区分“子序列”和“字串”，子序列只要求按照原有顺序排列，而字串还需要满足元素连续

这个问题通常都是使用动态规划来实现的。这里快速复习一下动态规划的做法：

定义 DP 数组：\mathtt{dp}_i 表示以 \mathtt{nums}_i 这个数结尾的 LIS 的长度。其中 \mathtt{dp} 为 DP 数组，\mathtt{nums} 为原序列。

为了方便讲述，下文的索引皆以 1 开始，且约定 i \in \mathbb{N}^+。但在代码中，索引的起始值遵循语言的规则。

那么基本状况为：对于 \forall i \in [1, n] 有 \mathtt{dp}_i = 1

那么，状态转移方程为：

迭代 \forall i \in [1, n] 有 \mathtt{dp}_i = \max\left\{\mathtt{dp}_i, \mathtt{dp}_j + 1\right\}，其中 j 是满足 j \in [1, i) 和 \mathtt{nums}_j < \mathtt{nums}_i 的所有值。

可以很容易地写出下面的 Java 代码：

为什么使用 Java？

因为 Java 的语法比较中规中矩、老老实实，没有太多特殊的语法糖，甚至有些啰嗦，所以更加方便使用不同语言的读者阅读。

放心，本文的重点是 LIS 的二分搜索解法，会给出多种语言的解。以后所有在《算法奇论》中的文章的主要算法代码都会使用多语言解，其他的使用 Java 或伪代码。

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];  // 初始化 DP 数组
    Arrays.fill(dp, 1);  // 基本状态
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);  // 状态转移
            }
        }
    }
    int res = 0;
    for (int i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);  // 求结果
    }
    return res;
}

时间复杂度 O(N^2)，空间复杂度 O(N)。

二分搜索？来看理论依据

说实话，一般人基本想不到这种解法，连大 OJ 平台洛谷、LeetCode 上有关二分搜索的解法都比较少，而且这个解法也不常用。但是放在这里，一方面是它的时间复杂度只有 O(N \log N)，可以处理较大规模的数据，另一方面是作为思维的拓展，开阔一下视野。

有趣的是，如果有人玩过纸牌游戏，那么可能就能想起这个解法。事实上，LIS 还跟一个叫做 patience game 的纸牌游戏有关，甚至还有一种算法就叫 patience sorting（耐心排序算法）。下面，一起来看。

给你一堆扑克牌，需要从左往右遍历所有的扑克牌，并将其分成若干堆。在将扑克牌分成若干堆时，需要按照如下规则执行：

  1. 只能把点数小的压在点数大于或等于它的牌上。
  2. 如果当前牌的点数较大导致没有可以放的已有的堆，那么新建一个堆，将其放入。
  3. 如果有多个堆可以选择，选择最左侧的堆（也就是最早创建的堆）放入。

例如如果有如下点数的扑克牌若干张：

为了方便看出大小关系，我们假设扑克牌只有数字点数，且点数范围不限

10  9  2  5  3  7  101  18

那么按照前面的规则迭代并分堆，其中 #a 表示触发了上面列出的三个规则的第 a 个：

----- Round 1 -----
10  9  2  5  3  7  1  101  18
^^
#2
@1: 10
----- Round 2 -----
9  2  5  3  7  1  101  18
^
#1
@1: 10  9
----- Round 3 -----
2  5  3  7  1  101  18
^
#1
@1: 10  9  2
----- Round 4 -----
5  3  7  1  101  18
^
#2
@1: 10  9  2
@2: 5
----- Round 5 -----
3  7  1  101  18
^
#1
@1: 10  9  2
@2: 5  3
----- Round 6 -----
7  1  101  18
^
#2
@1: 10  9  2
@2: 5
@3: 7
----- Round 7 -----
1  101  18
^
#3
@1: 10  9  2  1
@2: 5
@3: 7
----- Round 8 -----
101  18
^^^
#2
@1: 20  9  2  1
@2: 5
@3: 7
@4: 101
----- Round 9 -----
18
^^
#1
@1: 20  9  2  1
@2: 5
@3: 7
@4: 101  18

最后，所有扑克牌被我们分成了 4 堆，那么我现在可以直接告诉你：

堆数 4 就是最终答案，即 LIS 的长度。

什么？！这就出来了！那么为什么呢？又和二分搜索有何关系呢？

慢慢来，我们一点一点解释。

前方高能！数学证明大军来袭！

为什么遇到多个可选的堆，需要选择最左侧的堆呢？

因为这样可以保证每一个堆的堆顶有序。看被下划线包围的数字：

20  9  2  _1_
_5_
_7_
101  _18_
### 1 5 7 18 ###

证明：

我们将原来的扑克牌序列成员牌序列。

命名 H_i 为第 i 个牌堆的牌堆顶的点数，其中 i \in \left\{x \in \mathbb{N} | 1 \le x \le n\right\}，n 牌堆数量。将 m 定义为当前遍历到的牌的点数。

回顾前面的三个规则，我们能够推出以下隐含规则：

证毕。

看起来也不难嘛，我们将其命名为“性质一”。

为什么最终牌的堆数就是 LIS 的长度呢？

且看：

其中的一个 LIS。当然，不止一个。
20  9  _2_  1
_5_
_7_
_101_  18
### 2 5 7 101 ###

证明：

令 LIS 的长度为 l，牌堆的个数为 n，L_i 表示 LIS 的第 i 个数，其中 i 满足 i \in \left\{ x \in \mathbb{N} | 1 \le x \le l\right\}

同样根据我们分牌堆的三个规则，可以推出：

证毕。

好像也不是那么难理解。我们将其称为“性质二”。

那么理论分析结束，开始考虑如何编码吧！

如何编码？二分搜索保平安

现在我们要做的就是将上述分牌堆的逻辑转换为代码实现。那么我们来考虑，如何实现它？

首先我们得知道如何实现分堆。

其实也不难，遍历每一个值，然后根据其大小找到需要放入的堆即可。

而我们怎么知道该放入哪个堆呢？

根据上面证明的性质一，我们可以知道堆顶一定是递增排列的有序数列。那么这个时候我们就可以使用二分搜索来找对需要放入的堆。这里需要注意，我们要将牌放入合法的最左边的牌堆，意思就是说我们需要用二分搜索来找到左边界。

那么代码就显而易见了。我将给出多种语言的解法，这里是代码链接：https://www.luogu.com.cn/paste/1bqjd7gj

除部分内容参考以下资料外，上面的数学证明是自己琢磨出来的。

参考资料：