Leetcode 887. 鸡蛋掉落
1.题目基本信息
1.1.题目描述
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
1.2.题目地址
https://leetcode.cn/problems/super-egg-drop/description/
2.解题方法
2.1.解题思路
对1到n的x个位置，如果x处碎了，则找下面的x-1段的最小操作数dp[x-1]，同时次数的蛋只剩下k-1个；如果x处蛋没碎，则找上面的n-x段的的操作数dp[n-x]，此时剩余蛋还是k个。最终获取所有x中最小的步数。
2.2.解题步骤
第一步，状态定义，这里的状态函数的方式，因为状态转移时即会用到大的n状态，也会用到小的n的状态。其中状态函数的输入值为剩余鸡蛋数k和待查找的楼层层数，返回该状态下的得到分界楼层f的最小步数。
第二步，递归进行状态转移。上下两段楼层的步骤是分别是一个随当前楼层x的递减函数dp(k,n-x)和递增函数dp(k-1,x-1)，所以可以用二分法找到上下两段楼层中最大的步骤数的最小值。同时使用字典记忆每个已经获取的状态的值，减小程序开销。最终的dp(k,n)即为题解。
3.解题代码
Python代码
class Solution:# 对1到n的x个位置，如果x处碎了，则找下面的x-1段的最小操作数dp[x-1]，同时次数的蛋只剩下k-1个；如果x处蛋没碎，则找上面的n-x段的的操作数dp[n-x]，此时剩余蛋还是k个。最终获取所有x中最小的步数。# 第一步，状态定义，这里的状态函数的方式，因为状态转移时即会用到大的n状态，也会用到小的n的状态。其中状态函数的输入值为剩余鸡蛋数k和待查找的楼层层数，返回该状态下的得到分界楼层f的最小步数。# 第二步，递归进行状态转移。上下两段楼层的步骤是分别是一个随当前楼层x的递减函数dp(k,n-x)和递增函数dp(k-1,x-1)，所以可以用二分法找到上下两段楼层中最大的步骤数的最小值。同时使用字典记忆每个已经获取的状态的值，减小程序开销。最终的dp(k,n)即为题解。def superEggDrop(self, k: int, n: int) -> int:# dp(k,n)为k个鸡蛋的情况下，n层楼需要的最小操作次数（注意：这里的n层楼可以从中间的开始）memo={}def dp(k,n):if (k,n) not in memo:if n==0:result1=0elif k==1:result1=nelse:left,right=0,n+1 # 左开右开区间while left+1<right:x=(right-left)//2+leftval1=dp(k-1,x-1) # x的递增函数val2=dp(k,n-x) # x的递减函数# 求最后一个val1小于val2对应的x# 红：val1<=val2的x，蓝：val1>=val2的x；left始终指向红，right始终指向蓝（相等的数特殊处理，同时给予红蓝属性）if val1<val2:left=xelif val1>val2:right=xelse:left=right=x# 此时right指向最后一个val1<val2的x，left指向第一个val1>=val2的x# result1=1+min(dp(k,n-right),dp(k-1,left-1))result1=1+min(max(dp(k - 1, x - 1), dp(k, n - x))for x in (left, right))memo[(k,n)]=result1return memo[(k,n)]return dp(k,n)
4.执行结果
