05_鸡蛋掉落（Python）（unsolved）

骑猪看日落 2023-01-13 05:58 140阅读 0赞

### 目录 ###

*  鸡蛋掉落
 *  示例 1：
 *  示例 2：
 *  示例 3：
 *  提示：
 *  解答
 *   *  动态规划 + 二分查找
     *  思路和算法

# 鸡蛋掉落 #

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

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

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

# 示例 1： #

> **输入**：k = 1, n = 2  
> **输出**：2  
> **解释**：  
> 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。  
> 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。  
> 如果它没碎，那么肯定能得出 f = 2 。  
> 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

# 示例 2： #

> **输入**：k = 2, n = 6  
> **输出**：3

# 示例 3： #

> **输入**：k = 3, n = 14  
> **输出**：4

# 提示： #

*  1 <= k <= 100
 *  1 <= n <= 104

# 解答 #

难过头了似乎

## 动态规划 + 二分查找 ##

## 思路和算法 ##

我们可以考虑使用动态规划来做这道题，状态可以表示成 ( k , n ) (k,n) (k,n)，其中 k 为鸡蛋数，n 为楼层数。当我们从第 x 楼扔鸡蛋的时候：

如果鸡蛋不碎，那么状态变成$ (k, n-x)$，即我们鸡蛋的数目不变，但答案只可能在上方的  n − x n-x n−x 层楼了。也就是说，我们把原问题缩小成了一个规模为  ( k , n − x ) (k, n-x) (k,n−x)的子问题；

如果鸡蛋碎了，那么状态变成 ( k − 1 , x − 1 ) (k-1, x-1) (k−1,x−1)，即我们少了一个鸡蛋，但我们知道答案只可能在第 x 楼下方的 x − 1 x-1 x−1层楼中了。也就是说，我们把原问题缩小成了一个规模为 ( k − 1 , x − 1 ) (k-1, x-1) (k−1,x−1) 的子问题。

这样一来，我们定义 d p ( k , n ) dp(k,n) dp(k,n)为在状态 ( k , n ) (k, n) (k,n)下最少需要的步数。根据以上分析我们可以列出状态转移方程：

dp ( k , n ) = 1 + min ⁡ 1 ≤ x ≤ n ( max ⁡ ( dp ( k − 1 , x − 1 ) , dp ( k , n − x ) ) ) \\textit\{dp\}(k, n) = 1 + \\min\\limits\_\{1 \\leq x \\leq n\} \\Big( \\max(\\textit\{dp\}(k-1, x-1), \\textit\{dp\}(k, n-x)) \\Big) dp(k,n)=1\+1≤x≤nmin(max(dp(k−1,x−1),dp(k,n−x)))

这个状态转移方程是如何得来的呢？对于  d p ( k , n ) dp(k,n) dp(k,n)而言，我们像上面分析的那样，枚举第一个鸡蛋扔在的楼层数 x。由于我们并不知道真正的 f 值，因此我们必须保证 鸡蛋碎了之后接下来需要的步数 和 鸡蛋没碎之后接下来需要的步数 二者的 最大值 最小，这样就保证了在 最坏情况下（也就是无论 f 的值如何） d p ( k , n ) dp(k,n) dp(k,n)的值最小。如果能理解这一点，也就能理解上面的状态转移方程，即最小化  m a x ( d p ( k − 1 , x − 1 ) , d p ( k , n − x ) ) max(dp(k−1,x−1),dp(k,n−x)) max(dp(k−1,x−1),dp(k,n−x))。

如果我们直接暴力转移求解每个状态的 d p dp dp 值，时间复杂度是为  O ( k n 2 ) O(kn^2) O(kn2)，即一共有 O ( k n ) O(kn) O(kn)个状态，对于每个状态枚举扔鸡蛋的楼层 x，需要  O ( n ) O(n) O(n) 的时间。这无疑在当前数据范围下是会超出时间限制的，因此我们需要想办法优化枚举的时间复杂度。

我们观察到  dp ( k , n ) \\textit\{dp\}(k, n) dp(k,n) 是一个关于 n 的单调递增函数，也就是说在鸡蛋数 kk 固定的情况下，楼层数 n 越多，需要的步数一定不会变少。在上述的状态转移方程中，第一项  T 1 ( x ) = dp ( k − 1 , x − 1 ) \\mathcal\{T\_1\}(x) = \\textit\{dp\}(k-1, x-1) T1(x)=dp(k−1,x−1)是一个随 x 的增加而单调递增的函数，第二项 T 2 ( x ) = dp ( k , n − x ) \\mathcal\{T\_2\}(x) = \\textit\{dp\}(k, n-x) T2(x)=dp(k,n−x)是一个随着 x 的增加而单调递减的函数。

这如何帮助我们来优化这个问题呢？当 x 增加时， T 1 ( x ) \\mathcal\{T\_1\}(x) T1(x)单调递增而 T 2 ( x ) \\mathcal\{T\_2\}(x) T2(x)单调递减，我们可以想象在一个直角坐标系中，横坐标为 x，纵坐标为  T 1 ( x ) \\mathcal\{T\_1\}(x) T1(x)和  T 2 ( x ) \\mathcal\{T\_2\}(x) T2(x)。当一个函数单调递增而另一个函数单调递减时，我们如何找到一个位置使得它们的最大值最小呢？

![fig1][]

如上图所示，如果这两个函数都是连续函数，那么我们只需要找出这两个函数的交点，在交点处就能保证这两个函数的最大值最小。但在本题中， T 1 ( x ) \\mathcal\{T\_1\}(x) T1(x)和  T 2 ( x ) \\mathcal\{T\_2\}(x) T2(x) 都是离散函数，也就是说，x 的值只能取 1, 2, 3等等。在这种情况下，我们需要找到最大的满足  T 1 ( x ) < T 2 ( x ) \\mathcal\{T\_1\}(x) < \\mathcal\{T\_2\}(x) T1(x)<T2(x) 的  x 0 x\_0 x0，以及最小的满足  T 1 ( x ) ≥ T 2 ( x ) \\mathcal\{T\_1\}(x) \\geq \\mathcal\{T\_2\}(x) T1(x)≥T2(x)的$ x\_1$，对应到上图中，就是离这两个函数（想象中的）交点左右两侧最近的整数。

我们只需要比较在  x 0 x\_0 x0 和 x 1 x\_1 x1 处两个函数的最大值，取一个最小的作为 x 即可。在数学上，我们可以证明出  x 0 x\_0 x0和 x 1 x\_1 x1相差 11，这也是比较显然的，因为它们正好夹住了那个想象中的交点，并且相距尽可能地近。因此我们就可以使用二分查找的方法找出 x 0 x\_0 x0，再得到  x 1 x\_1 x1：

*  我们在所有满足条件的 x 上进行二分查找。对于状态 ( k , n ) (k, n) (k,n)而言，x 即为 \[ 1 , n \] \[1, n\] \[1,n\]中的任一整数；
 *  在二分查找的过程中，假设当前这一步我们查找到了  x mid x\_\\textit\{mid\} xmid ，如果 T 1 ( x mid ) > T 2 ( x mid ) \\mathcal\{T\_1\}(x\_\\textit\{mid\}) > \\mathcal\{T\_2\}(x\_\\textit\{mid\}) T1(xmid)>T2(xmid)，那么真正的 x 0 x\_0 x0一定在 x mid x\_\\textit\{mid\} xmid的左侧，否则真正的  x 0 x\_0 x0在  x mid x\_\\textit\{mid\} xmid的右侧。

二分查找的写法因人而异，本质上我们就是需要找到最大的满足  T 1 ( x ) < T 2 ( x ) \\mathcal\{T\_1\}(x) < \\mathcal\{T\_2\}(x) T1(x)<T2(x)的 x 0 x\_0 x0，根据  x mid x\_\\textit\{mid\} xmid进行二分边界的调整。在得到了 x 0 x\_0 x0后，我们可以知道  x 1 x\_1 x1即为  x 0 + 1 x\_0 + 1 x0\+1，此时我们只需要比较 max ⁡ ( T 1 ( x 0 ) , T 2 ( x 0 ) ) \\max(\\mathcal\{T\_1\}(x\_0), \\mathcal\{T\_2\}(x\_0)) max(T1(x0),T2(x0))和  max ⁡ ( T 1 ( x 1 ) , T 2 ( x 1 ) ) \\max(\\mathcal\{T\_1\}(x\_1), \\mathcal\{T\_2\}(x\_1)) max(T1(x1),T2(x1))，取较小的那个对应的位置作为 x 即可

这样一来，对于给定的状态 ( k , n ) (k, n) (k,n)，我们只需要  O ( log ⁡ n ) O(\\log n) O(logn) 的时间，通过二分查找就能得到最优的那个 x，因此时间复杂度从 O ( k n 2 ) O(kn^2) O(kn2)降低至 O ( k n log ⁡ n ) O(kn \\log n) O(knlogn)，可以通过本题。

class Solution:
        def superEggDrop(self, k: int, n: int) -> int:
            memo = { }
            def dp(k, n):
                if (k, n) not in memo:
                    if n == 0:
                        ans = 0
                    elif k == 1:
                        ans = n
                    else:
                        lo, hi = 1, n
                        # keep a gap of 2 x values to manually check later
                        while lo + 1 < hi:
                            x = (lo + hi) // 2
                            t1 = dp(k - 1, x - 1)
                            t2 = dp(k, n - x)
    
                            if t1 < t2:
                                lo = x
                            elif t1 > t2:
                                hi = x
                            else:
                                lo = hi = x
    
                        ans = 1 + min(max(dp(k - 1, x - 1), dp(k, n - x))
                                      for x in (lo, hi))
    
                    memo[k, n] = ans
                return memo[k, n]
    
            return dp(k, n)

操! 老子看不懂五五五五五五 还是太菜了~

[fig1]: /images/20221022/7faceedbd3f74ca3a111b3fea0dd602b.png