难度困难668收藏分享切换为英文接收动态反馈
给你?k?枚相同的鸡蛋，并可以使用一栋从第?1?层到第?n?层共有?n?层楼的建筑。
已知存在楼层?f?，满足?0 <= f <= n?，任何从?高于?f?的楼层落下的鸡蛋都会碎，从?f?楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层?x?扔下（满足?1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中?重复使用?这枚鸡蛋。
请你计算并返回要确定?f?确切的值?的?最小操作次数?是多少？
方法一：通用方法
dp(k,n)定义：k个鸡蛋在第n层楼扔dp(k,n)次恰好没有碎
这里有一个最大和最小的关系：
最小关系：求dp(k,n)的最小值
最大关系：恰好没有碎，求的是鸡蛋破碎发生在搜索区间穷尽时，即下图所示的最大值
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
memo = dict()
def dp(k,n):
if k == 1:return n
if n == 0:return 0
if (k,n) in memo:
return memo[(k,n)]
res = float('inf')
for i in range(1,n+1): #穷举搜索
res = min( res, #最小关系
max(dp(k,n-i),dp(k-1,i-1))+1 #最大关系
)
memo[(k,n)] = res
return res
return dp(k,n)方法二：使用二分法替换穷举搜索
那么注意 dp(K - 1, i - 1) 和 dp(K, N - i) 这两个函数， 其中 i 是从 1到 N 单增的， 如果我们固定 K 和 N ， 把这两个函数看做关于 i 的函数， 前者随着 i 的增加应该也是单调递增的， ?后者随着 i 的增加应该是单调递减的：
这时候求?者的较?值， 再求这些最?值之中的最?值， 其实就是求这个交点嘛， 熟悉?分搜索的同学肯定敏感地想到了， 这不就是相当于求Valley（??） 值嘛， 可以??分查找来快速寻找这个点的。
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
memo = dict()
def dp(k,n):
if k == 1:return n
if n == 0:return 0
if (k,n) in memo:
return memo[(k,n)]
res = float('inf')
left,right = 1,n #二分查找
while left <= right:
mid = int(left + (right - left)/2)
broken = dp(k-1,mid-1)
notbroken = dp(k,n-mid)
if broken > notbroken:
right = mid -1
res = min(res,broken +1)
else:
left = mid +1
res = min(res,notbroken +1)
memo[(k,n)] = res
return res
return dp(k,n)方法三：重新定义状态矩阵
dp[k][m]=n
当前有k个鸡蛋，最多可以尝试m次，在这个状态下能测试n层楼
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
dp = [[0]*(n+1) for i in range(k+1)]
m = 0
while(dp[k][m] < n):
m += 1
for k1 in range(1,k+1):
dp[k1][m] = dp[k1-1][m-1] + 1 + dp[k1][m-1]
return m
?
?