887. 鸡蛋掉落

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 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个鸡蛋，只能从低到高一层楼一层楼的遍历
• 有2个鸡蛋，100层楼，可以考虑分10层，这样最大需要19次，也可以考虑让第一个鸡蛋和第二个鸡蛋最大尝试次数之和均匀一点，
• 有k个鸡蛋，n层楼，dp[k, n]。选择任意扔鸡蛋的位置为x，则有两种情况且：
  • 鸡蛋碎了，则消耗一个鸡蛋，答案在x层下方的x-1楼层中。t1 = dp[k-1, x-1]
  • 鸡蛋没碎，则消耗0个鸡蛋，答案在x层上方剩下的n-x楼层中。t2 = dp[k, n-x]

接下来就是寻找x的位置，然后计算每个x的取值情况下的最小值。

关于x的函数t1和t2, t1单调递增，t2单调递减，二者分段函数的最小值在交点处，考虑离散函数特点，选交点左右两个数。

class Solution {
    unordered_map<int, int> memo;
    int dp(int k, int n){
        if (memo.find(n*100+k) == memo.end()){
            int ans;
            if (k == 1){
                ans = n;
            }else if (n <= 1){
                ans = n;
            }else{
                int low = 1, high = n;
                while (low + 1 < high){
                    int mid = (low+high)/2;
                    int t1 = dp(k-1, mid-1);
                    int t2 = dp(k, n-mid);
                    if (t1 < t2){
                        low = mid;
                    }else if(t1 > t2){
                        high = mid;
                    }else{
                        low = high = mid;
                    }
                }
                // cout << k << " " << n << endl;
                // cout << "low-high:" << low << " " << high << endl;
                // 抛鸡蛋的最佳点在low或high中之一
                ans = 1 + min(max(dp(k-1, low-1), dp(k, n-low)), max(dp(k-1, high-1), dp(k, n-high)));
            }
            memo[n*100+k] = ans;
        }
        return memo[n*100+k];
    }
public:
    int superEggDrop(int k, int n) {
        return dp(k, n);
    }
};

方法二：决策单调性

方法三：数学法