google经典算法面试题-鸡蛋问题

最近在 leetcode 上看到了一道题Super Egg Drop, 刚好之前看到过一到很类似的题，就是 google 的一道经典的面试题。这里记录一下自己整个的解题思路。

google 原题

给你两个鸡蛋，它们有可能都在某一层楼往下摔就会摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋摔碎的临界点。每次实验即使没摔碎也不会对鸡蛋有损耗。

思路

这是一道很经典的需要用到动态规划的题目，我们每一次扔鸡蛋的结果都会影响我们后续扔的次数，比方说我们上来就从 90 层扔，如果碎了，我们就得从1楼一层一层往上扔到90层才能试出结果，如果没碎，我们只需要在 90 ~ 100 这 10 层做实验即可。

要用动态规划的来解这道题，我们首先要列出问题中的状态 每次我们扔鸡蛋的时候，可能会出现两种状态

• 摔碎，这时下一个鸡蛋就要从最底层一个一个往上试才能试出结果
• 没碎，则我们需要根据剩余的楼层数来决策出我们下一次丢鸡蛋的楼层数

我们假设第一次我们从 x 层楼往下扔，如果鸡蛋没碎，下一次我们往上走 k 层楼再扔，根据我们的假设我们可以绘制出一个这样的决策树。

为了让最坏的情况不太坏，我们必须要保证每一次的决策最后所需要的次数都尽可能的相等。也就是 1 + k = x。所以每次鸡蛋没碎，我们都要再上一次上升楼层数的基础减少1。

如何确认第一次扔的高度

我们假设我们每次扔鸡蛋都没有碎，第一次从x层开始扔,我们最后一次就必须在100层楼扔了。可以得到式子 x + x - 1 + x - 2 ... + 1 >= 100,根据等差数列求和，我们可以得到 x * (x + 1)/2 >= 100, 得到 x >= 13.45,因为 x 只能取整数，所以第一次我们从14层楼开始扔，得到最坏情况下，我最多需要扔14次可以确认临界点。

放宽到一般情况，n 层楼 2 个鸡蛋，我们可以得到 x + x - 1 + x - 2 ... + 1 >= n 最后算出 x >=

Super Egg Drop

Super Egg Drop 这道题是 google 这道题的升级版。这里的是给定 K 个鸡蛋，N层楼让你求出最小的次数是多少。

我们还是按照动态规划的思路来列出问题中的状态：

• K = 0的时候，我们是试不出来的
• K = 1时，我们只能从1楼一层一层往上试，次数为楼层高度 n
• K = 2时，情况和上面一样
• k > 2时，需要我们单独分析了

我们设 dp[k][n] 为 k 个鸡蛋，n 层楼时的最优次数。

• k = 0 , dp[k][n] = 0
• k = 1, dp[k][n] = n
• k = 2, dp[k][n] =

  

当 k > 2时

假设我们还剩 m 个鸡蛋，还需要实验 n 层楼，此时 1 <= n <= h, 假设我们已经知道了 1 ~ n 层最优解，假设这时候第一次丢的高度为 y ，丢的时候会出现两种情况, 然后可以列出动态方程

碎了

则此时的最优解为 dp(m - 1, y - 1) + 1

没碎

则此时的最优解为 dp(m, n - y) + 1

由此我们可以得到 dp(m, n) = min(max(dp(m - 1, y - 1), dp(m, n - y)) + 1), 1<=y< n，由此我们可以递推的得到 dp(K,N)

JS 实现源码

这题后面还需要优化，由于复杂度较高，需要一定的基础，暂时没有继续优化下去

推荐一个人的博客，把这题分析的非常透彻，有兴趣的可以看看博客地址