扔鸡蛋

---

image.png

二分查找排除楼层的速度无疑是最快的，那干脆先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？

很遗憾，并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。

如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次。

• 求最坏情况下的最少扔鸡蛋次数，[N,M]可以转换成[0,M-N]的问题

带记忆dp

• 动态规划算法的时间复杂度就是子问题个数 × 函数本身的复杂度 = ，k是鸡蛋个数，n是楼高。

子问题个数也就是不同状态组合的总数，即两个状态的乘积 ，子问题复杂度

// 带记忆dp伪代码
def dp(K, N):
    for 1 <= i <= N:
        # 最坏情况下的最少扔鸡蛋次数
        res = min(res, 
                  max( 
                        dp(K - 1, i - 1), # 碎
                        dp(K, N - i)      # 没碎
                     ) + 1 # 在第 i 楼扔了一次
                 )
    return res

带记忆的dp暴力穷举[0,n]

class Solution:
    def __init__(self):
        self.d={}
    def helper(self,k,n):
        if (k,n) in self.d:
            return self.d[(k,n)]
        if k==1 or n==0:
            return n
        # k蛋数 n楼数
        res=10**4
        for i in range(n+1):
            # 碎了 [0,i] 没碎 [i+1,n]
            res=min(res,max(self.helper(k-1,i),self.helper(k,n-i-1))+1)
        # print(k,n,res)
        self.d[(k,n)]=res
        return res
    def superEggDrop(self, k: int, n: int) -> int:
        return self.helper(k,n)

优化

楼层数与dp的解成正比

• 动态规划算法的时间复杂度就是子问题个数 × 函数本身的复杂度 =

class Solution:
    def __init__(self):
        self.d={}
    def helper(self,k,n):
        # k==1 只有一个鸡蛋 return n || n==0 只有最后一种可能 => return 0 不需要跳了
        if k==1 or n==0:
            return n
        if (k,n) in self.d:
            return self.d[(k,n)]
        # k蛋数 n楼数
        res=10**6
        l=0
        r=n
        # l==r 不需要跳了,不断查找最优mid，计算不同mid下的
        # 计算不同 [0,mid],[mid+1,n]组合下的dp
        while(l<r):
            mid=(l+r)//2
            # 寻求最坏(大)的情况下的最优(小)解
            # [0,mid]
            broken=self.helper(k-1,mid)
            # [mid+1,r]
            not_broken=self.helper(k,n-mid-1)
            if broken > not_broken:
                res=min(res,broken+1)
                r=mid
            else:
                res=min(res,not_broken+1)
                l=mid+1
        self.d[(k,n)]=res
        return res
    def superEggDrop(self, k: int, n: int) -> int:
        return self.helper(k,n)