leetcode扔鸡蛋问题总结

扔鸡蛋问题是一道经典的面试题&＃xff0c;他的简单一点的问法是给两个鸡蛋&＃xff0c;一百层楼&＃xff0c;找到最少的尝试次数&＃xff0c;找到鸡蛋不会摔碎的临界楼层。

这个问题的解法有这么几种&＃xff0c;二分法&＃xff0c;平方根法&＃xff0c;解方程法&＃xff0c;具体的解释可以看一下这个博客&＃xff0c;这里详细说一下最优解法解方程法&＃xff0c;

假设问题存在最优解(扔鸡蛋过程),这个解的最坏情况尝试次数是x次,那么,我们第一次扔鸡蛋该选择哪一层?

恰恰是从第x层开始扔,选择更高一层或是更低一层都不合适

为什么第一次扔就要选择第x层呢?

这里的解释也是通过假设法,然后演绎,有些烧脑,小伙伴们坚持住:

假设第一次扔在第x&＃43;1层(比x大):

如果第一个鸡蛋碎了&＃xff0c;那么第二个鸡蛋只能从第1层开始一层一层扔&＃xff0c;一直扔到第x层。

这样一来&＃xff0c;我们总共尝试了x&＃43;1次&＃xff0c;和假设尝试x次相悖。由此可见&＃xff0c;第一次扔的楼层必须小于x&＃43;1层。

假设第一次扔在第x-1层(比x小)&＃xff1a;

如果第一个鸡蛋碎了&＃xff0c;那么第二个鸡蛋只能从第1层开始一层一层扔&＃xff0c;一直扔到第x-2层。

这样一来&＃xff0c;我们总共尝试了x-2&＃43;1 &＃61; x-1次&＃xff0c;虽然没有超出假设次数&＃xff0c;但似乎有些过于保守。

假设第一次扔在第x层&＃xff1a;

如果第一个鸡蛋碎了&＃xff0c;那么第二个鸡蛋只能从第1层开始一层一层扔&＃xff0c;一直扔到第x-1层。

这样一来&＃xff0c;我们总共尝试了x-1&＃43;1 &＃61; x次&＃xff0c;刚刚好没有超出假设次数。

因此&＃xff0c;要想尽量楼层跨度大一些&＃xff0c;又要保证不超过假设的尝试次数x&＃xff0c;那么第一次扔鸡蛋的最优选择就是第x层。

归纳

如果第一次扔鸡蛋没有碎,我们的尝试消耗了一次,问题就转化成了两个鸡蛋在100-x层楼往下扔,要求尝试次数不得超过x-1次

所以第二次尝试的楼层跨度是x-1层,绝对楼层是x&＃43;(x-1)层

同理,如果鸡蛋还没有碎,第三次楼层跨度是x-2,第四次是x-3

根据总结,可以列出一个楼层数的方程式:

x &＃43; (x-1) &＃43; (x-2) &＃43; ... &＃43; 1 &＃61; 100

下面我们来解这个这个方程:

(x&＃43;1)*x/2 &＃61; 100

最终x向上取整,得到 x&＃61;14

因此&＃xff0c;最优解在最坏情况的尝试次数是14次&＃xff0c;第一次扔鸡蛋的楼层也是14层。

最后&＃xff0c;让我们把第一个鸡蛋没碎的情况下&＃xff0c;所尝试的楼层数完整列举出来&＃xff1a;

14&＃xff0c;27&＃xff0c; 39&＃xff0c; 50&＃xff0c; 60&＃xff0c; 69&＃xff0c; 77&＃xff0c; 84&＃xff0c; 90&＃xff0c; 95&＃xff0c; 99&＃xff0c; 100

这个问题进阶一点的问法就是leetcode上887题&＃xff0c;

K 个鸡蛋&＃xff0c;并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的&＃xff0c;如果一个蛋碎了&＃xff0c;你就不能再把它掉下去。
你知道存在楼层 F &＃xff0c;满足 0 <&＃61; F <&＃61; N 任何从高于 F 的楼层落下的鸡蛋都会碎&＃xff0c;从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动&＃xff0c;你可以取一个鸡蛋&＃xff08;如果你有完整的鸡蛋&＃xff09;并把它从任一楼层 X 扔下&＃xff08;满足 1 <&＃61; X <&＃61; N&＃xff09;。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何&＃xff0c;你确定 F 的值的最小移动次数是多少&＃xff1f;


这个题&＃xff0c;鸡蛋不再是2个&＃xff0c;楼层也不确定&＃xff0c;一般使用动态规划来解决。

假设我们第一个鸡蛋扔出的位置在第X层&＃xff08;1<&＃61;X<&＃61;M&＃xff09;&＃xff0c;会出现两种情况&＃xff1a;

1.第一个鸡蛋没碎

那么剩余的M-X层楼&＃xff0c;剩余N个鸡蛋&＃xff0c;可以转变为下面的函数&＃xff1a;

F&＃xff08;M-X&＃xff0c;N&＃xff09;&＃43; 1&＃xff0c;1<&＃61;X<&＃61;M

2.第一个鸡蛋碎了

那么只剩下从1层到X-1层楼需要尝试&＃xff0c;剩余的鸡蛋数量是N-1&＃xff0c;可以转变为下面的函数&＃xff1a;

F&＃xff08;X-1&＃xff0c;N-1&＃xff09; &＃43; 1&＃xff0c;1<&＃61;X<&＃61;M

整体而言&＃xff0c;我们要求出的是 N层楼 / K个鸡蛋 条件下&＃xff0c;最大尝试次数最小的解&＃xff0c;所以这个题目的状态转移方程式如下&＃xff1a;

X可以为1......N,所以有M个Max&＃xff08; F&＃xff08;N-X&＃xff0c;K&＃xff09;&＃43; 1&＃xff0c; F&＃xff08;X-1&＃xff0c;K-1&＃xff09; &＃43; 1&＃xff09;的值,最终F(N,K)是这M个值中的最小值,即最优解

F&＃xff08;N&＃xff0c;K&＃xff09;&＃61; Min&＃xff08;Max&＃xff08; F&＃xff08;N-X&＃xff0c;K&＃xff09;&＃43; 1&＃xff0c; F&＃xff08;X-1&＃xff0c;K-1&＃xff09; &＃43; 1&＃xff09;&＃xff09;&＃xff0c;1<&＃61;X<&＃61;N

代码&＃xff1a;

class Solution {public int superEggDrop(int K, int N) {//k&＃61;eggs,N&＃61;floorint[][] dp &＃61; new int[K&＃43;1][N&＃43;1];for (int i&＃61;0;i<&＃61;N;i&＃43;&＃43;) {//首先是eggs&＃61;0的情况dp[0][i] &＃61; 0;//然后是eggs&＃61;1的情况//eggs&＃61;1的时候&＃xff0c;肯定是从第0层一直往上实验dp[1][i] &＃61; i;}//再考虑floors的边界for (int i&＃61;1;i<&＃61;K;i&＃43;&＃43;) {//首先是floors&＃61;0的情况dp[i][0] &＃61; 0;//然后是floors&＃61;1的情况dp[i][1] &＃61; 1;}//状态转移方程dp[m][n] &＃61; min(max(dp[m-1][n-1]&＃43;1,dp[m][n-1]&＃43;1))for(int i&＃61;2;i}

这个解法复杂度还是不满足要求的&＃xff0c;将继续寻找更好的方法。