扔鸡蛋

作者: 小幸运Q | 来源:发表于2021-04-08 00:13 被阅读0次

image.png

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

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

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

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

带记忆dp

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

子问题个数也就是不同状态组合的总数,即两个状态的乘积 O(KN),子问题复杂度O(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的解成正比
  • 动态规划算法的时间复杂度就是子问题个数 × 函数本身的复杂度 = O(knlog_2(n))
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)

相关文章

  • 扔鸡蛋

    二分查找排除楼层的速度无疑是最快的,那干脆先用二分查找,等到只剩 1 个鸡蛋的时候再执行线性扫描,这样得到的结果是...

  • 扔鸡蛋

    扔鸡蛋,有egg个鸡蛋,楼高度为floor层。问,至少扔几次,才能确定鸡蛋最多在哪一层,不碎

  • 有趣的扔鸡蛋问题

    题目:扔鸡蛋问题 有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎...

  • 谷歌“扔鸡蛋问题”

    问题: 假设有2个鸡蛋和100层楼,将鸡蛋从第n层扔下,鸡蛋没有碎,将鸡蛋从n+1层扔下,鸡蛋碎了,那么n层就...

  • 动态规划-扔鸡蛋

    动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程[https://bai...

  • 【LintCode】254. 丢鸡蛋

    楼有 n 层高,鸡蛋若从 k 层或以上扔,就会碎。从 k 层以下扔,就不会碎。现在给两个鸡蛋,用最少的扔的次数找到...

  • 漫画:有趣的扔鸡蛋问题

    本文转载自程序员小灰 ————— 第二天 ————— 题目:扔鸡蛋问题 有2个鸡蛋,从100层楼上往下扔,以此...

  • 画外音

    (画面) 一位老人正在忙于做菜。“叭”,磕开一鸡蛋,倒碗里,蛋壳扔拉圾袋里,“叭”再磕开一鸡蛋,倒碗里,蛋壳扔...

  • 高楼扔鸡蛋解题思路

    1. 带「备忘录」的递归算法 把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子...

  • 徐伊万扔番茄我儿子扔鸡蛋

    回湖北过年的这几天在家看《囧妈》。 做为一位两个娃的老妈,在看到 徐伊万一个一个地往窗外扔小番茄的场景时想起儿子在...

网友评论

      本文标题:扔鸡蛋

      本文链接:https://www.haomeiwen.com/subject/kpwpkltx.html