题目：
给你 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 <= k <= 1001 <= n <= 104
思路：
我们可以考虑使用动态规划来做这道题，状态可以表示成 (k,n)，其中 k 为鸡蛋数，n 为楼层数。当我们从第 x 楼扔鸡蛋的时候：
如果鸡蛋不碎，那么状态变成 (k, n−x)，即我们鸡蛋的数目不变，但答案只可能在上方的 n−x 层楼了。也就是说，我们把原问题缩小成了一个规模为 (k, n−x) 的子问题；
如果鸡蛋碎了，那么状态变成 (k−1, x−1)，即我们少了一个鸡蛋，但我们知道答案只可能在第 x 楼下方的 x−1 层楼中了。也就是说，我们把原问题缩小成了一个规模为 (k−1, x−1) 的子问题。
这样一来，我们定义 dp(k, n) 为在状态 (k,n) 下最少需要的步数。根据以上分析我们可以列出状态转移方程：
dp(k,n) = 1+ 1≤x≤n {min (max(dp(k−1,x−1), dp(k,n−x))) }
这个状态转移方程是如何得来的呢？对于 dp(k, n) 而言，我们像上面分析的那样，枚举第一个鸡蛋扔在的楼层数 x。由于我们并不知道真正的 f 值，因此我们必须保证 鸡蛋碎了之后接下来需要的步数 和 鸡蛋没碎之后接下来需要的步数 二者的 最大值 最小，这样就保证了在 最坏情况下（也就是无论 f 的值如何） dp(k, n) 的值最小。如果能理解这一点，也就能理解上面的状态转移方程，即最小化 max(dp(k−1,x−1), dp(k,n−x))。
如果我们直接暴力转移求解每个状态的 dp 值，时间复杂度是为 O(kn^2)，即一共有 O(kn) 个状态，对于每个状态枚举扔鸡蛋的楼层 x，需要 O(n) 的时间。这无疑在当前数据范围下是会超出时间限制的，因此我们需要想办法优化枚举的时间复杂度。
我们观察到 dp(k,n) 是一个关于 n 的单调递增函数，也就是说在鸡蛋数 k 固定的情况下，楼层数 n 越多，需要的步数一定不会变少。在上述的状态转移方程中，第一项 T1(x) = dp(k−1, x−1) 是一个随 x 的增加而单调递增的函数，第二项 T2(x) = dp(k, n−x) 是一个随着 x 的增加而单调递减的函数。
这如何帮助我们来优化这个问题呢？当 x 增加时，T1(x) 单调递增而 T2(x) 单调递减，我们可以想象在一个直角坐标系中，横坐标为 x，纵坐标为 T1(x) 和 T2(x)。当一个函数单调递增而另一个函数单调递减时，我们如何找到一个位置使得它们的最大值最小呢？
如上图所示，如果这两个函数都是连续函数，那么我们只需要找出这两个函数的交点，在交点处就能保证这两个函数的最大值最小。但在本题中，T1(x) 和 T2(x) 都是离散函数，也就是说，x 的值只能取 1,2,3 等等。在这种情况下，我们需要找到最大的满足 T1(x) < T2(x) 的 x0，以及最小的满足 T1(x) ≥ T2(x) 的 x1，对应到上图中，就是离这两个函数（想象中的）交点左右两侧最近的整数。
我们只需要比较在 x0 和 x1 处两个函数的最大值，取一个最小的作为 x 即可。在数学上，我们可以证明出 x0 和 x1 相差 1，这也是比较显然的，因为它们正好夹住了那个想象中的交点，并且相距尽可能地近。因此我们就可以使用二分查找的方法找出 x0，再得到 x1：
我们在所有满足条件的 x 上进行二分查找。对于状态 (k,n) 而言，x 即为 [1,n] 中的任一整数；
在二分查找的过程中，假设当前这一步我们查找到了 xmid，如果 T1(xmid) > T2(xmid)，那么真正的 x0 一定在 xmid 的左侧，否则真正的 x0 在 xmid 的右侧。
二分查找的写法因人而异，本质上我们就是需要找到最大的满足 T1(x) < T2(x) 的 x0 ，根据 xmid 进行二分边界的调整。在得到了 x0 后，我们可以知道 x1 即为 x0 + 1，此时我们只需要比较 max( T1(x0), T2(x0) ) 和 max( T1(x1), T2(x1) )，取较小的那个对应的位置作为 x 即可。
这样一来，对于给定的状态 (k,n)，我们只需要 O(logn) 的时间，通过二分查找就能得到最优的那个 x，因此时间复杂度从 O(kn^2) 降低至 O(knlogn)，可以通过本题。
代码：
class Solution {
public:
unordered_map<int, int> memo;
int dp(int k, int n) {
if (memo.find(n * 100 + k) == memo.end()) {
int ans;
if (n == 0) ans = 0;
else if (k == 1) ans = n;
else {
int lo = 1, hi = n;
while (lo + 1 < hi) {
int x = (lo + hi) / 2;
int t1 = dp(k - 1, x - 1);
int t2 = dp(k, n - x);
if (t1 < t2) lo = x;
else if (t1 > t2) hi = x;
else lo = hi = x;
}
// 二分查找之后， lo 和 hi 就是 x0 与 x1
ans = 1 + min(max(dp(k - 1, lo - 1), dp(k, n - lo)), max(dp(k - 1, hi - 1), dp(k, n - hi)));
}
memo[n * 100 + k] = ans;
}
return memo[n * 100 + k];
}
int superEggDrop(int k, int n) {
return dp(k, n);
}
};