扔鸡蛋（leetcode_887）
你将获得 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 <= K <= 100 1 <= N <= 10000 这题是一道经典的面试题，dabuladong那本书和leetcode官方都有很详细的讲解，我感觉这一题我理解得一知半解，估计多段时间可能会忘了，提醒下自己要记得重写一遍。 这题是动态规划，第一种定义动态规划数组的方法是达到K和N的状态需要的次数，这个次数呢是最坏的情况，意思就是达到这个次数后一定能找到那个楼层的。于是我们就可以知道这个最简单的办法就是以N为循环变量扫描一遍，对于每个N都计算最坏的情况，就是dp[K, N - N_i]和dp[K - 1, N_i - 1]的最大值，然后在所有最大值里面取最小的那个d**p(K,N)=1+1≤X≤Nmin(max(d**p(K−1,X−1),d**p(K,N−X)))
这里我们可以优化下，我们可以肯定知道这个循环有单调性，就是搜索难度是随楼层N的增加而增加的，于是就可以利用二分搜索。
\ /
\ /
\ /
我们就是要找dp中N – N_i和N_i相遇的那个点。
代码如下：
class Solution
{
public:
int superEggDrop(int K, int N)
{
return dp(K, N);
}
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) >> 1;
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;
}
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];
}
private:
unordered_map<int, int> memo;
};
我们还可以换个思路，就是dp数组记录的是T次尝试最多可以试的楼层，这样的话，我们就可以等当dp等于N的时候取T就行了。
class Solution
{
public:
int cal(int K, int T)//此处的定义是给你K个鸡蛋，最多能尝试T次，最坏的情况下能测试的楼层数
{
if (T == 1 || K == 1)
return T + 1;
return cal(K - 1, T - 1) + cal(K, T - 1);
}
int superEggDrop(int K, int N)
{
int T = 1;
while (cal(K, T) < N + 1)
T++;
return T;
}
};
这个思路也可以二分搜索，不过我没写，这题我还没轮回贯通，之后还要重写下。