目录
高楼扔鸡蛋
这是一个比较经典的动态规划问题，最先来自谷歌的面试题。
题目
方法一：动态规划
分析
我们假设 \(g(k, n)\) 表示当有 \(k\) 枚鸡蛋，楼层数为 \(n\) 时，找到临界楼层 \(F\) 所需要的最小操作次数。
边界条件
当楼层数为零时，查找次数为 \(0\) ，当鸡蛋数量为 \(1\) 时，我们需要一层一层地查找，因此，最坏的情况下，查找次数等于楼层数 \(n\)，因此：
\[\begin{gather*} g(0, i) = 0, \quad 1 \le i \le n\\ g(1, i) = n, \quad 1 \le i \le n \end{gather*} \]状态转移
我们考虑一般情况，对于第 \(i\) 层楼：
\[\underbrace{1,\ 2,\ \cdots, \ i-1}, \ i, \underbrace{\ i+1,\ \cdots,\ n-1, \ n} \]当我们从第 \(i\) 层楼扔下一枚鸡蛋的时候，这枚鸡蛋有两种状态，鸡蛋碎了或者不碎，那么：
-
若鸡蛋没有碎
我们可以继续用 \(k\) 枚鸡蛋，在上方的楼层，即 \(i + 1, \cdots, n\)，共 \(n - i\) 层楼中，继续寻找 \(F\)，因此，所需要查找的次数为 \(g_1=g(k, n - i)\) ；
-
若鸡蛋碎了
这时，鸡蛋的数量少了一枚，因此，我们就需要用剩余的 \(k - 1\) 枚鸡蛋，在下方的楼层，即 \(1, \cdots, i - 1\)，共 \(i - 1\) 层楼中，继续寻找 \(F\)，因此所需要查找的次数为 \(g_2=g(k - 1, i - 1)\) 。
这里，我们可以看到，通过状态转移，明显将问题的规模缩小了，由于题目是要求在最坏的情况下，扔鸡蛋的最少次数，所以，最坏的情况下，在第 \(i\) 层楼的操作次数，取决于 \(g_1\) 和 \(g_2\) 的最大值。
因此，在最坏的情况下，最少的操作次数为：
\[g(k,n) = \min^n_{i=1}(\max(g_1, \ g_2)) = \min^n_{i=1}(\max(g(k, n - i), \ g(k - 1, i - 1))) \]代码实现
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
"""
:param k: the number of eggs
:param n: the number of floor
:return: 最坏情况下最少的尝试次数
"""
memory = dict()
min_count = self.drop_egg(k, n, memory)
return min_count
def drop_egg(self, eggs: int, floor: int, memory: Dict) -> int:
# 边界条件：如果楼层数量为0，查找次数为0
if floor == 0:
return 0
# 如果只剩一个鸡蛋，就必须一层一层地查找
if eggs == 1:
return floor
if (eggs, floor) in memory:
return memory.get((eggs, floor))
result = float("INF")
for i in range(1, floor + 1):
result = min(result, max(self.drop_egg(eggs, floor - i, memory), self.drop_egg(eggs - 1, i - 1, memory)) + 1)
memory[(eggs, floor)] = result
return result
复杂度
复杂度分析：
- 时间复杂度：\(O(kn^2)\)；
- 空间复杂度：\(O(kn)\)。
注：这种方法，直接枚举所有的状态，在力扣上提交的时候，会超时，因此，我们还需要对上述算法做进一步优化。
方法二
分析
结合前面的分析，我们可以看出：
- \(g_1=g(k, \ n - i), \ 1 \in [i, n]\) 是一个随 \(i\) 增加的单调递减函数；
- \(g_2=g(k - 1, \ i - 1),\ 1 \in [i, n]\) 是一个随 \(i\) 增加的单调递增函数；
因此，
标签：return,floor,鸡蛋,次数,高楼,memory,动态,eggs From： https://www.cnblogs.com/larry1024/p/17057913.html