Python版-LeetCode 学习：887. 鸡蛋掉落

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：输入：K = 1, N = 2    输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-egg-drop

方法1：递归加剪枝

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        memo={}
        # 递归方法，加记录中间值(对二叉树进行减枝)
        def dp(K,N):
            # 初始情况判定
            if K==1: return N
            if N==0: return 0

            # 占存记录（K，N）成对值 memo
            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-1,i-1),dp(K,N-i))+1)
            # 二分线性搜索
            low,high=1,N
            while low<=high:
                mid=(low+high)//2
                # 碎了：K-1,mid-1
                brekon=dp(K-1,mid-1)
                # 不碎：K,N-mid
                not_brekon=dp(K,N-mid)
                # 当碎大于不碎的情况时，楼层上限high=mid-1，结果集
                if brekon>not_brekon:
                    high=mid-1
                    # 
                    res=min(res,brekon+1)
                else:
                    low=mid+1
                    res=min(res,not_brekon+1)
            # 记录一存在(K,N)的尝试次数
            memo[(K,N)]=res
            return res
        return dp(K,N)

方法2：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp=[[0 for j in range(N+1)] for i in range(K+1)]
        # 测试次数
        m=0
        # dp[K][m] == N，也就是给你 K 个鸡蛋，测试 m 次，最坏情况下最多能测试 N 层楼。
        # 以下两层循环，类似于两个for，基本要达到的效果就遍历出（K，m）组合的最大值
        while dp[K][m]<N:
            m+=1
            for k in range(1,K+1):
                # 总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）
                # dp[k][m - 1] 就是楼上的楼层数，因为鸡蛋个数 k 不变，也就是鸡蛋没碎，扔鸡蛋次数 m 减一；
                # dp[k - 1][m - 1] 就是楼下的楼层数，因为鸡蛋个数 k 减一，也就是鸡蛋碎了，同时扔鸡蛋次数 m 减一。
                dp[k][m]=dp[k][m-1]+dp[k-1][m-1]+1
        
        return m

 方法3：

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # 对方法2的简化，用一维数组代替二维数组
        dp = [0] + [1]*K  
        F = 1
        while dp[K]<N:
            # 遍历K
            for k in range(K,0,-1):
                # 
                dp[k] += dp[k-1] + 1
            F += 1
        return F