两枚鸡蛋的鸡蛋掉落：单峰性、决策单调性、差分方程

摘要: 单峰性、二分优化 DP

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本题是基于各种单调性设计算法的经典例子，也是基于目标函数的单峰性、决策单调性优化 DP 的经典例子。从算法的大框架看，有动态规划和值域二分两套框架。

对于动态规划方法，基于最优化目标函数的单峰性可以做二分优化 DP、继续观察目标函数可以发现其中的决策单调性，可以进一步优化。参考文章 单峰性与二分优化DP：N个鸡蛋掉落问题。

对于值域二分方法，在判定的时候需要走另一个动态规划，其结果在后续的判定中可以复用，因此直接从小到大推导DP即可。另一方面，DP 的转移方程可以作为差分方程求解出来，那么在二分判定的时候就可以 $O(1)$ 地给出判定结果了。参考文章 求解差分方程/函数方程优化DP：N个鸡蛋掉落问题。

1884. 鸡蛋掉落-两枚鸡蛋

给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。

每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

提示：

1 <= n <= 1000

示例 1：
输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。

示例 2：
输入：n = 100
输出：14
解释：
一种最优的策略是：

• 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
• 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
• 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
  不管结果如何，最多需要扔 14 次来确定 f 。

算法1：动态规划

若鸡蛋有 1 个，则测出 n 层未知楼层需要 n 次操作。

下面考虑鸡蛋味 2 个的情况。定义 $dp[k]$ 表示有两个鸡蛋时，测量 k 个未知楼层的最小步数。这样初始值为 $dp[0] = 0$，答案为 $dp[H]$，状态转移方程如下：

$$\begin{align} dp[k] &= \min\limits_{1 \leq j \leq k} \max(1 + j - 1, 1 + dp[k-j]) \\ &= 1 + \min\limits_{1 \leq j \leq k} \max(j - 1, dp[k-j]) \\ \end{align}$$

状态共 $H$ 个，状态转移需要 $O(H)$，时间复杂度为 $O(H^{2})$。

代码 (Python)

class Solution:
    def twoEggDrop(self, H: int) -> int:

        @lru_cache(int(1e8))
        def solve(k: int) -> int:
            if k == 0:
                return 0

            ans = k
            for j in range(1, k + 1):
                ans = min(ans, 1 + max(j - 1, solve(k - j)))

            return ans

        return solve(H)

优化1：二分优化DP

回顾状态转移方程：

$$dp[k] = 1 + \min\limits_{1 \leq j \leq k} \max(j - 1, dp[k-j])$$

记 $f(j, k) = \max(j - 1, dp[k-j])$。由于楼层数越高，所需的最少步数就会越大，因此 $dp[j]$ 关于 $j$ 是单调递增的，$dp[k - j]$ 关于 $j$ 是单调递减的，另一方面，$j - 1$ 是单调递增的。

因此 $f(j, k)$ 关于 $j$ 是单峰函数。可以通过三分的方法求极值，这里是离散的情况，也可以用二分，具体过程如下：

对于给定的 $k$，在 $j$ 的范围 $[1, k]$ 内二分，对于当前二分的 $mid$，记 $T_{1} = j - 1, T_{2} = dp[k - j]$：

• 如果 $T_{1} < T_{2}$，说明 $mid$ 取小了，置 $left = mid + 1$；
• 如果 $T_{1} > T_{2}$，说明 $mid$ 取大了，置 $right = mid - 1$；
• 如果 $T_{1} = T_{2}$，说明已找到最优决策。

状态共 $O(H)$ 个，状态转移需要 $O(\log H)$，随意总时间复杂度为 $O(H\log H)$。

代码(Python)

class Solution:
    def twoEggDrop(self, H: int) -> int:

        @lru_cache(int(1e8))
        def solve(k: int) -> int:
            if k == 0:
                return 0

            ans = k
            # 二分地从 [1, k] 中找 j
            left = 1
            right = k
            while left <= right:
                mid = (left + right) // 2
                T1 = mid - 1
                T2 = solve(k - mid)
                ans = min(ans, max(T1, T2) + 1)
                if T1 > T2:
                    right = mid - 1
                elif T1 < T2:
                    left = mid + 1
                else:
                    # 找到最优决策
                    break

            return ans

        return solve(H)

优化2：决策单调性

回顾状态转移方程：

$$dp[k] = 1 + \min\limits_{1 \leq j \leq k} \max(j - 1, dp[k-j])$$

$T_{1}(j)$ 是 $j$ 的单调递增函数，与 $k$ 无关；$T_{2}(j) = dp[k-j]$ 是单调递减函数，如果视其为一条曲线，那么当 $k$ 变化时，$T(k-j)$ 构成曲线族，并且随着 $k$ 增加，曲线向右上平移，如下图：

记 $p = opt(k)$ 表示 $dp[k]$ 的最优决策点，可以看出，随着 $k$ 增加，最优决策点的位置 $opt(k)$ 也增加，也就是构成决策单调性。

由上述决策单调性，因此在推导 $dp[k]$ 时，$j$ 在小于 $opt(k-1)$ 的值上不可能取到最优。但是 $opt(k-1), opt(k-1)+1, \cdots, k$ 范围内在哪取到极值的问题还是要解决。

这里有一个基于问题的额外性质，本质也是前面二分算法用到的单峰性。记 $T_{1}(j) = j - 1, T_{2}(j) = dp[k - j]$，则最优决策 $opt(k)$ 为：

• 满足 $\max(T_{1}(j), T_{2}(j)) \leq \max(T_{1}(j+1), T_{2}(j+1))$ 的最小的 $j$；
• 或者是 $T_{1}(j) \geq T_{2}(j)$ 的最小的 $j$。

于是在推导 $k$ 时，可以用一个变量 $j$ 记录最优决策，并用上述两个性质之一推进 $j$。事实上推进的部分就是上图中的 $opt(k-1)$ 到 $opt(k)$。

共 $H$ 个状态，状态转移的时间复杂度摊销 $O(1)$，总时间复杂度 $O(H)$。

代码 (Python)

class Solution:
    def twoEggDrop(self, H: int) -> int:
        dp = [0] * (H + 1)
        j = 1 # 最优决策随着 k 增加而增加
        for k in range(1, H + 1):
            while j <= k and j - 1 < dp[k - j]:
                j += 1
            dp[k] = 1 + max(j - 1, dp[k - j])
        return dp[H]

算法2：值域二分+动态规划

我们要求的是，给定 2 个鸡蛋和楼层 $H$，测完所有的 $H$ 未知范围所需的最小操作次数。

如果考虑给定 2 个鸡蛋和操作次数 $m$，最多可以测多少楼层，记其为 $f(m)$，通过问题背景可以知道 $f(m)$ 随 $m$ 单调增加，即操作步数 $m$ 越多，则可以测的楼层 $f(m)$ 越多。

因此可以用值域二分算法，初始时 $[left, right] = [1, H]$，如果 $f(mid) < H$，则答案一定大于 $mid$；否则答案小于等于 $mid$。

下面的问题是 $f(m)$ 如何计算。定义 $dp[i]$ 表示 2 个鸡蛋操作 $i$ 次，最多可以测出多少楼层，于是 $f(m) = dp[m]$。

如果是 1 个鸡蛋，那么 $i$ 次操作可以测出 $i$ 层。现在考虑第 $2$ 个鸡蛋，假设测试第 $x$ 层：

• 如果没碎，那么 $x$ 及其下面的层均已知，鸡蛋依然是 2 个，$x$ 上面可以再测 $dp[i - 1]$ 层。如果 $x$ 下面有 $a$ 层，一共测出 $dp[i-1] + 1 + a$ 层。
• 如果碎了，那么 $x$ 及其上面的层均已知，还剩 1 个鸡蛋，$x$ 下面可以再测 $i - 1$ 层。如果 $x$ 上面有 $b$ 层，一共测出 $i + b$ 层。

给定了 $a, b$ 之后，不论鸡蛋是否碎，$x$ 下面能测出的层数为 $\min(i - 1, a)$、$x$ 上面能测出的层为 $\min(b, dp[i-1])$，汇总起来，有：

$$dp[i] = \max_{a, b}(1 + \min(a, i - 1) + \min(b, dp[i - 1]))$$

$g(a) = \min(a, i - 1), h(b) = \min(b, dp[i - 1])$ 的图像如下：

可以直观看出 $dp[i] = 1 + i - 1 + dp[i - 1] = i + dp[i - 1]$。

在值域二分的过程中如果按照上述动态规划的流程求 $f(m)$，则最坏需要 $O(H)$，这样值域二分的时间复杂度为 $O(H\log H)$。

---

但是这里有个性质，到在算 $f(m)$ 的过程中，实际上 $f(1), f(2), \cdots, f(m)$ 都算出来了。假设当前二分中点为 $mid$，则计算 $f(mid)$ 的过程顺便就算了 $f(1),f(2),\cdots,f(mid-1)$，过程中算到哪个 $f(i) \geq H$，直接就可以返回 $i$ 而不用等到 $mid$ 算完；如果算完了 $f(mid)$ 依然小于 $H$，那么就需要继续算 $f(mid + 1), f(mid + 2),\cdots$。

因此，这里可以直接按照 $f(1), f(2), \cdots$ 来算，算到某个 $f(i) \geq H$ 时返回即可。

假设 $i$ 推导到 $c$ 时 $dp[c] \geq H$，则时间复杂度为 $O(c)$，通过对 $i$ 与 $f(i)$ 关系的观察，以及一定的推导（参考后面的求解差分方程部分），可以得到时间复杂度为 $O(\sqrt{H})$。

代码 (Python)

class Solution:
    def twoEggDrop(self, H: int) -> int:
        # dp[i] 表示 2 个鸡蛋操作 i 次最多可以测出多少层
        dp = [0] * (H + 1)
        dp[0] = 0
        for i in range(1, H):
            dp[i] = i + dp[i - 1]
            if dp[i] >= H:
                return i
        return H

求解差分方程优化DP

回顾前面的状态转移方程：

$$dp[i] = i + dp[i - 1]$$

将其视为一个差分方程，求解出来，得到 $dp[i] = \frac{1}{2}i(i+1)$。这可以算是一种推公式优化 DP。

于是在二分的时候，检查 $f(m) = dp[m] = \frac{1}{2}m(m+1)$ 与 $H$ 的关系即可。

时间复杂度 $O(\log H)$。

代码 (Python)

class Solution:
    def twoEggDrop(self, H: int) -> int:
        left = 1
        right = H
        while left < right:
            mid = (left + right) // 2
            if mid * (mid + 1) // 2 < H:
                left = mid + 1
            else:
                right = mid
        return left

---