详解谷歌经典面试题-“鸡蛋掉落”

谷歌出过一道经典面试题，国内多家公司也常用来筛选候选人，来看看吧：

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？ 提示：

• 1 <= k <= 100
• 1 <= n <= 104

https://leetcode-cn.com/problems/super-egg-drop/

首先，读完这道题之后，不要觉得浪费粮食，或者觉得这事无聊，冷静！它只是一道算法题而已~

好了，开始解题~

先说个算法小技巧，凡是遇到给你n个数或者字符，然后让你求某种场景下的最小值或者最大值的题，大多数都跟动态规划相关，本题也不例外。解题步骤很简单，三步走即可：

按照上图，我们逐步来解下本题：

第 1 步：大事化小 (求状态转移方程)

假设当有k个鸡蛋，n层楼的时候，要确定 f 确切的值的最小操作次数是ans = dp(k, n)次。当我们从x楼扔鸡蛋的时候，只会出现以下两种情况：

• 鸡蛋碎了：鸡蛋个数少了1个，f的值范围是[0, x-1]，这个时候我们就把本问题缩小成了又一个小问题，即ans1 = dp(k-1, x-1)。举例：2个鸡蛋，4层楼，如果从2楼扔下鸡蛋，鸡蛋碎了，那么鸡蛋接下来要在1楼扔下试试的，所以这个时候，就演变成了1个鸡蛋1层楼的问题；
• 鸡蛋没碎：那么鸡蛋个数k不变，f的值范围是[n-x, n]， 这个时候我们就把本问题缩小成了一个小问题，即ans2 = dp(k, n-x)。举例：2个鸡蛋，4层楼，如果从2楼扔下鸡蛋，鸡蛋没碎，那么鸡蛋接下来要在3楼甚至4楼再扔下试试的，所以这个时候，就演变成了2个鸡蛋2层楼的问题；

通过以上分析，不管从x楼扔下的鸡蛋碎没碎，我们的尝试扔的次数一定得能得出确切的f，因此，加上在x楼扔的那1次，ans = dp(k, n) = 1 + Math.max(ans1, ans2) = 1 + Math.max(dp(k-1, x-1), dp(k, n-x))。举例：1. 在x楼碎了，需要ans1=100次；2. 在x楼没碎，需要的ans2=101次。最后得出确切的f，得考虑最坏情况，因此最后至少得尝试101次。

至此，我们得出了初步的状态转移方程，也知道x的取值范围是[1, n]，但是确切的x是几呢，我们最后要得出最大的f，且最小的尝试次数ans。就像你扔鸡蛋的时候，在k和n确定的情况下，x可以是[1, n]里的任何一个值，但是为了保

至此我们知道，扔鸡蛋的时候，在k和n确定的情况下，x可以是[1, n]里的任何一个值。但是为了f最大且ans最小，我们要遍历计算x的取值，以此得到最小的ans。此时最终的状态转移方程应该是：

ans = 1 + min( max(dp(k-1, x-1), dp(k, n-x)))；（1<=x<=n）

第 2 步：小事化了 (设置边界条件或者求初始值)

做算法题的时候，一定要看下取值范围，上限一般用不着，但是下限很有用，因为它基本上决定了我们的边界条件。按照本题提示，k和n都是大于1的，所以我们要求出k和n为1的时候，ans的值。

• k=1，只有1个鸡蛋的时候，不管n是几，一定都得从1楼开始，然后一层一层的尝试扔鸡蛋，直到鸡蛋碎了或者到了楼顶为止。如果你一下子跑到8楼扔鸡蛋，结果鸡蛋碎了，那你就再没有鸡蛋去扔了，你永远也得不到n了。因此，dp(1, n) = n。（哈哈，不要抬杠说再去多买几个鸡蛋~）
• n=1，只有1层楼，不管你有几个鸡蛋，只扔1个鸡蛋看碎不碎，就知道结果了。因此，dp(k, 1) = 1。（也不要抬杠想n个鸡蛋扔n次，浪费~）
• k=0或者n=0，没鸡蛋或者没楼层，没什么好尝试的，结果为0。注意虽然题意写明了k和n都是大于0的，但是因为我们等下要用递归，k和n是要慢慢减小范围的，因此还是会出现k与n为0的情况。

通过以上2步，其实我们已经能够写出下面的代码了。

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
// k个鸡蛋，n层楼
var superEggDrop = function(k, n) {
    return dp(k, n)

    function dp(k, n) {
        if(k===0 || n===0) {
            return 0
        }

        if(k===1) {
            return n
        } 

        if(n==1) {
            return 1
        }
        // x  [1, n]
        let ans = null
        for(let x= 1; x<=n; x++) {
            let tem = 1 + Math.max(dp(k-1, x-1), dp(k, n-x)) 
            if(ans===null) {
                ans = tem
            } else {
                ans = Math.min(ans, tem)
            }
        }
        return ans
    }
}

虽然上面代码能够通过小数值的测试用例，但是在LeetCode提交却显示超出时间限制。为什么？因为解法太暴力了，递归虽好，但不能地狱般不断调用啊！。接下来，我们要尝试第 3 步做优化了。

第 3 步：优化：记忆求值、有效求值等

3.1 记忆求值

刚刚做递归的时候，dp(k, n-x)与dp(k-1, x-1)的递归求解过程中是有重复性的，如都需要遍历到n为0的时候，如果每次都重复递归，很费时间，所以这个时候我们可以记忆求值，把k与n与ans的值对记录下来，这个时候我们可以考虑字典结构，但是字典结构的key只能是一个，并且根据题意我们知道1<=k<=100，因此我们可以定义一个Map，key为n*100+k，而value是ans，代码如下：

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
// k个鸡蛋，n层楼
var superEggDrop = function(k, n) {
    const  memo = new Map()
    return dp(k, n)
    function dp(k, n) {
        if(!memo.has(n*100+k)) {
            let ans = null
            if(k===0 || n===0) {
                ans = 0
            } else if(k===1) {
                ans = n
            } else if(n==1) {
                ans = 1
            } else {
                // x  [1, n]
                for(let x= 1; x<=n; x++) {
                    let tem = 1 + Math.max(dp(k-1, x-1), dp(k, n-x)) 
                    if(ans===null) {
                        ans = tem
                    } else {
                        ans = Math.min(ans, tem)
                    }
                }
            }
            memo.set(n*100 + k, ans)
        }
        return memo.get(n*100+k)
    }
}

但是提交LeetCode，依然超出时间限制。

3.2 有效求值

通过前面，我们已经写出代码，但是因为不计成本的全部递归，导致时间成本巨高。比如说，你家丢了一只鹅，然后你满地球去找，从南极找到北极，连太平洋海平面下两百米都想捞几下。结果会怎样，劳民伤财，做了好多无用功。正确的寻找方式应该是：在你家方圆两里地找下，找到就好开心，找不到就是找不到了，你家鹅不可能躲到太平洋去，又不是鹅鱼，所以别瞎折腾。

回到这道题，我们也要想办法避免掉不必要的递归比较，怎么避免呢。先来看函数式ans2= dp(k, n-x)与ans1 = dp(k-1, x-1)，其中k和n是常量。回顾下初中数学，这就是单调函数呀，其中ans2 = dp(k, n-x)中随着x的增大而单调递减，ans1 = dp(k-1, x-1)中随着x的增大而单调递增，这个时候我们怎么找到x，使得ans1与ans2的最大值最小呢？

当函数 f(x) 的自变量在其定义区间内增大（或减小）时，函数值f(x)也随着增大（或减小），则称该函数为在该区间上具有单调性。 https://baike.baidu.com/item/%E5%8D%95%E8%B0%83%E6%80%A7/6194133

如上图所示，很明显，交叉点就是使得ans1与ans2的最大值最小的交界点，但是注意这里的x指的是楼层，因此x必须是整数，我们只需要比较x0与x1处两个函数的最大值，取一个最小的作为x即可。

接下来，我们需要先找到x0，因为x在[1, n]中，而x是楼层，也就是有序数组，因此我们可以通过二分查找来找x0。从数学上可知，x1 = x0 + 1。此时我们再比较ans1与ans2的大小就可以了。

代码如下：

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
// k个鸡蛋，n层楼
var superEggDrop = function(k, n) {
    const  memo = new Map()
    return dp(k, n)
    
    function dp(k, n) {
        if(!memo.has(n*100+k)) {
            let ans = null
            if(k===0 || n===0) {
                ans = 0
            } else if(k===1) {
                ans = n
            } else if(n==1) {
                ans = 1
            } else {
                // 二分查找x
                let low = 1, high = n, ans1, ans2
                while(low+1<high){
                    let x = (low+high)>>1
                     ans1 = dp(k-1, x-1)
                     ans2 = dp(k, n-x)
                    if(ans1<ans2) {
                        low = x
                    } else if(ans1>ans2) {
                        high = x
                    } else {
                        low = high = x
                    }
                }
                ans1  = Math.max(dp(k - 1, low - 1), dp(k, n - low))
                ans2 = Math.max(dp(k - 1, high - 1), dp(k, n - high))
                ans = 1 + Math.min(ans1, ans2)
            }
            memo.set(n*100 + k, ans)
        }
        return memo.get(n*100+k)
    }
}

以上，如果你懂了，恭喜，你已经掌握了动态规划的精髓：大事化小小事化了，最后来个优化。