LeetCode 887. Super Egg Drop
You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.
You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.
Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.
Return the minimum number of moves that you need to determine with certainty what the value of f is.
Example 1:
Input: k = 1, n = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know that f = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
If it does not break, then we know f = 2.
Hence, we need at minimum 2 moves to determine with certainty what the value of f is.
Example 2:
Input: k = 2, n = 6
Output: 3
Example 3:
Input: k = 3, n = 14
Output: 4
Constraints:
1 <= k <= 100
1 <= n <= 104
解析：
你面前有一栋从 1 到N共N层的楼，然后给你K个鸡蛋（K至少为 1）。现在确定这栋楼存在楼层0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于F的楼层都会碎，低于F的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层F呢？
也就是让你找摔不碎鸡蛋的最高楼层F，但什么叫「最坏情况」下「至少」要扔几次呢？我们分别举个例子就明白了。
比方说现在先不管鸡蛋个数的限制，有 7 层楼，你怎么去找鸡蛋恰好摔碎的那层楼？
最原始的方式就是线性扫描：我先在 1 楼扔一下，没碎，我再去 2 楼扔一下，没碎，我再去 3 楼……
以这种策略，最坏情况应该就是我试到第 7 层鸡蛋也没碎（F = 7），也就是我扔了 7 次鸡蛋。
先在你应该理解什么叫做「最坏情况」下了，鸡蛋破碎一定发生在搜索区间穷尽时，不会说你在第 1 层摔一下鸡蛋就碎了，这是你运气好，不是最坏情况。
现在再来理解一下什么叫「至少」要扔几次。依然不考虑鸡蛋个数限制，同样是 7 层楼，我们可以优化策略。
最好的策略是使用二分查找思路，我先去第(1 + 7) / 2 = 4层扔一下：
如果碎了说明F小于 4，我就去第(1 + 3) / 2 = 2层试……
如果没碎说明F大于等于 4，我就去第(5 + 7) / 2 = 6层试……
以这种策略，最坏情况应该是试到第 7 层鸡蛋还没碎（F = 7），或者鸡蛋一直碎到第 1 层（F = 0）。然而无论那种最坏情况，只需要试log7向上取整等于 3 次，比刚才尝试 7 次要少，这就是所谓的至少要扔几次。
思路分析：
对动态规划问题，直接套我们以前多次强调的框架即可：这个问题有什么「状态」，有什么「选择」，然后穷举。
「状态」很明显，就是当前拥有的鸡蛋数K和需要测试的楼层数N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。
「选择」其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路，二分查找每次选择到楼层区间的中间去扔鸡蛋，而线性扫描选择一层层向上测试。不同的选择会造成状态的转移。
现在明确了「状态」和「选择」，动态规划的基本思路就形成了：肯定是个二维的dp数组或者带有两个状态参数的dp函数来表示状态转移；外加一个 for 循环来遍历所有选择，择最优的选择更新状态：
# 当前状态为 K 个鸡蛋，面对 N 层楼 # 返回这个状态下的最优结果 int dp(int K, int N): int res for 1 <= i <= N: res = min(res, 这次在第 i 层楼扔鸡蛋) return res
这段伪码还没有展示递归和状态转移，不过大致的算法框架已经完成了。
我们选择在第i层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。注意，这时候状态转移就来了：
如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；
如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼。
base case分析：
base case 很容易理解：当楼层数N等于 0 时，显然不需要扔鸡蛋；当鸡蛋数K为 1 时，显然只能线性扫描所有楼层：
代码如下：
class Solution {
public:
int superEggDrop(int K, int N) {
vector> dp(N + 1, vector(K + 1, 0));
// 初始化dp数组
for (int n = 0; n <= N; n++) dp[n][1] = n;
//状态转移方程
for (int n = 1; n <= N; n++)
for (int k = 2; k <= K; k++) {
int res = INT_MAX;
for (int j = 1; j <= n; j++)//第一次从哪扔？从第1层开始试
res = min(res, max(dp[j-1][k-1], dp[n-j][k]) + 1);
dp[n][k] = res;
}
return dp[N][K];
}
};
此种方法因时间复杂度太高，导致无法通过leetcode。
方法优化：
二分查找法，待改进的部分是最内层的循环，即第一次从哪层扔时，不再是从第1层开始挨着试，而是使用二分法试。
二分搜索的优化的核心是状态转移方程的单调性，首先简述一下原始动态规划的思路：
1、暴力穷举尝试在所有楼层1 <= i <= N扔鸡蛋，每次选择尝试次数最少的那一层；
2、每次扔鸡蛋有两种可能，要么碎，要么没碎；
3、如果鸡蛋碎了，F应该在第i层下面，否则，F应该在第i层上面；
4、鸡蛋是碎了还是没碎，取决于哪种情况下尝试次数更多，因为我们想求的是最坏情况下的结果。
核心的状态转移代码是这段：
当前状态为 K 个鸡蛋，面对 N 层楼
返回这个状态下的最优结果
def dp(K, N):
for 1 <= i <= N:
# 最坏情况下的最少扔鸡蛋次数
res = min(res,
max(
dp(K - 1, i - 1), # 碎
dp(K, N - i) # 没碎
) + 1 # 在第 i 楼扔了一次
)
return res
这个 for 循环就是下面这个状态转移方程的具体代码实现：
如果能够理解这个状态转移方程，那么就很容易理解二分查找的优化思路。
首先我们根据dp(K, N)数组的定义（有K个鸡蛋面对N层楼，最少需要扔几次），很容易知道K固定时，这个函数随着N的增加一定是单调递增的，无论你策略多聪明，楼层增加测试次数一定要增加。
那么注意dp(K – 1, i – 1)和dp(K, N – i)这两个函数，其中i是从 1 到N单增的，如果我们固定K和N，把这两个函数看做关于i的函数，前者随着i的增加应该也是单调递增的，而后者随着i的增加应该是单调递减的：
这时候求二者的较大值，再求这些最大值之中的最小值，其实就是求这两条直线交点，也就是红色折线的最低点嘛。
都很有可能可以运用二分查找来优化线性搜索的复杂度，回顾这两个dp函数的曲线，我们要找的最低点其实就是这种情况：
具体代码如下：
class Solution {
public:
int superEggDrop(int K, int N) {
vector> dp(K+1, vector(N+1));
for(int j=1; j <= N; j++)
dp[1][j] = j;
for(int i=2; i <= K; i++)
{
for(int j=1; j <= N; j++)
{
dp[i][j] = j;
int left = 1,right = j;
while(left < right)
{
int mid = (left+right)/2;
if(dp[i-1][mid-1] < dp[i][j-mid])
left = mid + 1;
else
right = mid;
}
dp[i][j]=min(dp[i][j], max(dp[i-1][right-1], dp[i][j-right])+1);
}
}
return dp[K][N];
}
};
转自：
About Author
