【问题求解II-HW5.A】高楼抛鸡蛋

引子

这是一个十分有趣的问题。我们首先思考扔鸡蛋到底意味着什么：

• 一个鸡蛋如果在 $x$ 层扔下去没碎，说明 $X\geq x$，否则 $X<x$。
• 鸡蛋碎与不碎是有区别的：如果所有鸡蛋都碎了但我们仍没有找出 $X$，那就寄了。

基于这些观察，我们先进行一些简单情况的思考：

• 如果我们手里只有一个鸡蛋，那么我们没有犯错空间，只能从一楼开始一层一层往上扔，次数为 $O(n)$。
• 如果我们手里有两个鸡蛋，那我们的策略应该是这样的：用第一个鸡蛋把一个大致的范围框出来——例如选择在 $l_1=1, l_2, \cdots, l_m=n$ 这些点扔鸡蛋，把范围缩小到某个 $[l_i, l_{i+1})$ 后，再用第二个鸡蛋一层层试过去。这个策略很像之前提过的“分块”。如果我们选取那些 $\sqrt n$ 的倍数位置作为第一轮的节点，则抛鸡蛋次数为 $O(\sqrt n)$。
• ……

动态规划 (I)

我们可以看到“用前面的鸡蛋的牺牲为后面的鸡蛋缩小范围”是一个核心思路。对于更多数量的鸡蛋，硬想已经很难想得清楚。考虑使用动态规划。

一个非常直接的动态规划状态设计是：令 $dp(k, n)$ 表示手里有 $k$ 个鸡蛋，要确定 $n$ 层大楼的答案，最少需要扔几次 (这个状态设计和原问题的描述是完全一致的)。转移考虑第一次应该在哪一层扔鸡蛋。如果第一次在第 $i$ 层扔鸡蛋，有两种情况：

• 鸡蛋碎了，则需要用 $k-1$ 个鸡蛋在 $1\cdots i-1$ 层确定答案。
• 鸡蛋没碎，则需要用 $k$ 个鸡蛋在 $i\cdot n$ 层确定答案。

这两种情况会落入哪一种是我们无法预知的，但为了保证找出答案，求次数时应该对其取 max。不过第一次在哪里扔是我们可以决定的，所以我们可以遍历所有可能的第一层，对所有情况取 min (请仔细体会取min/max的逻辑)。因此状态转移方程为

$$ dp(k, n) = \min_{1\leq i\leq n}\left(\max\{dp(k-1,i-1)+1, dp(k, n-i+1)+1\}\right) $$

该算法的空间复杂度为 $O(kn)$，时间复杂度为 $O(kn^2)$。对于本题来说仍需要优化。

基于状态转移方程单调性的优化

我们将 $dp(k, n)$ 看作关于 $k$ 和 $n$ 的二元函数，来观察它的单调性。容易发现它关于 $n$ 是单调增的 (大楼高度增加扔的次数肯定更多)。再次观察上述的状态转移方程，可以发现随着 $i$ 的增大，第一项 $dp(k-1, i-1)$ 一直在变大，第二项 $dp(k, n-i+1)$ 一直在变小。如果画成图的话大概是这样：

可以看到，状态转移方程中的函数 (绿色) 是单峰的 (即形如二次函数)。它在红色和蓝色线相等的地方取到最小值。因此对于每个 $dp(k, n)$，我们可以通过二分查找而不是一一枚举的方式寻找取到最小值的点 (红色减蓝色的结果是单调的)，时间复杂度优化至 $O(kn\log n)$。(注意：图上的红色和蓝色线是连续的，而实际问题中 dp 数组是离散的，因此你实际需要找的是“红色和蓝色差值最小的地方”。)

基于决策单调性的优化

在这个思路的基础上还可以进一步优化。我们令 $M_{k, n}$ 表示使得 $dp(k, n)$ 取到最小值的状态转移方程中的那个 $i$。朴素方法通过枚举确定 $M_{k, n}$，第一版优化通过二分查找确定 $M_{k, n}$，这里我们利用决策单调性均摊 $O(1)$ 地确定 $M_{k, n}$。

如果把 $M_{k, n}$ 看作关于 $k$ 和 $n$ 的函数，我们容易发现它关于 $n$ 是单调递增的。

• 直觉上，大楼的总层数增高了，那么第一次扔鸡蛋的位置肯定应该相对应地调高，否则如果鸡蛋没碎，上面待探索的层数就会太多。
• 严谨地计算上，对于 $dp(k, n)$ 问题，$M_{k, n}$ 满足 $dp(k-1, M_{k, n}) = dp(k, n-M_{k, n}+1)$。那么对于 $dp(k, n+1)$ 问题， $$ dp(k-1, M_{k,n}) = dp(k, n-M_{k, n}+1) \overset{dp关于n的单调性}{\leq} dp(k, (n+1) - M_{k, n} + 1) $$ 因此必然有 $M_{k, n+1}\geq M_{k, n}$。

$M_{k, n}$ 是每轮的最优点，也称为决策点。所以 $M_{k, n}$ 满足的单调性质称为决策单调性。基于决策单调性，对于每个 $k$，我们在计算 $M_{k, n}$ 时，不用从 1 开始枚举，而可以从 $M_{k, n-1}$ 开始枚举。因为 $dp(k, *)$ 一层中所有的 $M_{k, *}$ 的枚举合起来复杂度为 $O(n)$，所以算法的总时间复杂度降至 $O(kn)$。

动态规划 (II)

动态规划 (I) 的优点在于它选择从一个非常自然的状态设计出发解决问题，整个思维过程没有大的跃迁点。但缺点在于对优化能力的要求较高，如果水平不足很可能卡在 $O(kn^2)$ 的位置无法前进。这里我们介绍另一种动态规划的状态设计，它的状态和转移都有点“神之一手”的意味，但一旦想到整个问题就变得非常简单。

令 $dp(k, m)$ 表示用 $k$ 个鸡蛋扔 $m$ 次，最多可以在多高的楼层范围内确定答案 (例如 $dp(1, m)=m$，因为一个鸡蛋只能从1楼开始一层层往上)。考虑如何转移：在这种状态设计下，我们可以精确地确定第一次该在哪里扔鸡蛋。因为鸡蛋如果碎了，我们就要用 $k-1$ 个鸡蛋在 $m-1$ 次内找出答案，而这个条件下能确定的最大层数恰好是 $dp(k-1, m-1)$。所以我们第一轮应该在第 $dp(k-1, m-1) + 1$ 层扔鸡蛋。另外，如果鸡蛋没碎，我们还可以用 $k$ 个鸡蛋扔 $m-1$ 次，从而最多可以再向上探索 $dp(k, m-1)$ 层，因此状态转移方程为

$$ dp(k, m) = dp(k-1, m-1) + 1 + dp(k, m-1) $$

剩下的问题是，对于每个 $k$，$m$ 要枚举到多大？由于 $dp(k, m)$ 关于 $m$ 单调递增，所以我们只要枚举到 $dp(k, m)\geq n$ 的 $m$ 即可。一件显然的事情是 $m\leq n$，因此复杂度的一个上界是 $O(kn)$，这已经足够优秀了¹。

基于“信息论”的思路

这个解法的思路比较清奇，仅供大家欣赏。令 $f(k, m)$ 表示用 $k$ 个鸡蛋，扔 $m$ 次可以确定答案的最多楼层数，我们其实可以不借助任何基础推导，直接给出数学结果²:

$$ f(k, m) = \sum_{i=1}^k\binom{m}{i} $$

它的道理来自以下的分析：

用 $k$ 个鸡蛋扔 $m$ 次这个实验的本质，是建立一个从仅包含0和1的状态字符串到最终答案的映射。这里 01 串至多 $m$ 位，表示每次扔鸡蛋的结果，0 是碎了，1 是没有碎。因为我们只有 $k$ 个鸡蛋，所以 01 串里至多只能有 $k$ 个 0。注意两个细节：

• 如果从头到尾鸡蛋都没有碎过，那么我们不可能知道答案 (因为没有上界)，所以全 1 的串无效。
• 如果串中有 $k$ 个 0，那么最后一个必须是 0 (因为鸡蛋碎完了就没有鸡蛋可扔了)。

因此合法的状态共有

$$ \sum_{i=1}^{k-1}\binom{m}{i} + \sum_{i=k}^m\binom{i-1}{k-1} $$

其中前面一个求和表示包含小于 $k$ 个 0 的合法字符串的个数，后面一个求和表示恰好 $k$ 个 0 的合法字符串的个数。后面一类由于固定了一个 0 在字符串末尾，所以只有 $k-1$ 个可支配的 0 (注：我们认为组合数 $n$ 选 $m$ 如果 $n<m$ 则值为 0，这与广义组合数的定义相容)。通过简单的数学推导你可以发现 $\displaystyle \sum_{i=k}^m\binom{i-1}{k-1}=\binom{m}{k}$ (将第一项 $\displaystyle\binom{k-1}{k-1}$ 改写为 $\displaystyle \binom{k}{k}$，然后采用“滚雪球法”)，或者你也可以通过思维推导发现如果在这种字符串的末尾添加占位符将其长度补到 $m$，本质上就是 $\displaystyle \binom{m}{k}$。总之，合法的状态总数为

$$ \sum_{i=1}^k\binom{m}{i} $$

鸡蛋落地的结果序列必须可以和楼层建立一一映射，否则一定存在无法分辨的两个楼层 (可以参考使用决策树证明基于比较的排序算法的复杂度下界的过程来理解这句话)，所以答案的上界是 $\sum_{i=1}^k\binom{m}{i}$。又因为每次鸡蛋碎与不碎会将我们引导到两个不相交的区域 ($[1, x-1]$ 和 $[x, n]$) 进行下一步操作，所以这个上界是可以做到的。因此 $f(k, m)=\sum_{i=1}^k\binom{m}{i}$。进一步地，你可以发现我们在此处定义 0 为碎的巧妙之处：将所有状态串按照字典序从小到大排序，排在第 $i$ 位的字符串恰好就是确定第 $i$ 层的扔法。

有了这个结果，我们可以直接二分 $m$，然后计算 $f(k, m)$ 并与 $n$ 比较。时间复杂度 $O(k\log n)$。