此题目曾出现在vivo2020提前批招聘笔试题目之中，将题目简单的改为高楼检测手机质量，但解法完全一样。

题目描述

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例

示例 1：
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2：
输入：K = 2, N = 6
输出：3

示例 3：
输入：K = 3, N = 14
输出：4

问题分析

• 状态：鸡蛋数量和楼层高度。
• 选择：鸡蛋是否破裂。
• 状态转移方程：
  情况有两种：1.当前楼层鸡蛋如果破裂，那么应该从下面一层接着测试，即broken = dp(k-1,n-1)。2.当前楼层鸡蛋如果没有破裂，那么应该从上面一层接着测试，即not_broken = dp(k,n-mid)。
  if broken > not_broken:应该从鸡蛋破裂的下一层开始测试。if broken <= not_broken:鸡蛋应该更上一层楼再行测试。
• 为了减少搜索时间，我们采用二分法来寻找令鸡蛋破裂的楼层（C++）。

class Solution {
public:
    
    unordered_map<int,int>memory;
    int helper(int K, int N){
        if (K == 1) return N;
        if (N == 0) return 0;
        int low = 1;
        int high = N;
        int res = INT_MAX;

        if (memory.count(N * 100 + K) > 0)
            return memory[N * 100 + K];
        while (low <= high){
            int mid = low + (high - low)/2;
            int broken = helper(K-1, mid-1);
            int not_broken = helper(K, N-mid);
            if (broken > not_broken){
                high = mid - 1;
                res = min(res, broken + 1);
            }
            else{
                low = mid + 1;
                res = min(res, not_broken + 1);
            }
        }
        memory[N * 100 + K] = res;
        return res;
    }
    int superEggDrop(int K, int N) {
        return helper(K,N);
    }
};

时间复杂度：dp问题的时间复杂度是子问题的个数乘以函数本身的时间复杂度。本题中二分搜索的时间复杂度为O(logn)，子问题个数为状态的数量KN，所以总体上上时间复杂度是O(KNlogn),空间复杂度为O(KN)。