LeetCode 鸡蛋掉落（最清晰的解法）_扔鸡蛋 leetcode

你将获得 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 是多少。
1
2
3
4
5
6
7

示例 2：

输入：K = 2, N = 6
输出：3
1
2

示例 3：

输入：K = 3, N = 14
输出：4
1
2

提示：

1 <= K <= 100
1 <= N <= 10000
1
2

$思路分析：$这道题就是非常绕，让人感觉好像答案只与鸡蛋的数量有关系。但这答题遇到了老衲，老衲定要解开它的真面目。话不多说，开始解题。

难点一：这道题的“移动”是不受空间限制的，我们潜意识里可能会认为它是爬楼的次数，
认为在上次扔鸡蛋的位置进行爬楼转移到下一个位置所移动楼层的数目。
蛋式题目并不是这个意思，题干说“每次移动，把它从任一楼层 X 扔下”，也就是说 $你可以测试多少次或者说你可以仍多少次鸡蛋$。

难点二：对于折半查找数的游戏大家都应该知道，所以对于[1, 2,3,4 …, N]这些楼层，我们使用折半查找的思路先在(N + 1) / 2这一楼层丢鸡蛋，判断是否破碎。
如果鸡蛋碎了，则F在[1, (N + 1) / 2 - 1]，否则鸡蛋没有碎，F在[(N + 1) / 2, N]。
这样给人的感觉就是只和鸡蛋的数量有关，如果鸡蛋够，使用二分法来测试，则必定会测试出F，如果鸡蛋不够。
蛋式你有没有想过，如果你有无数个鸡蛋，蛋我只给你1次移动（“扔鸡蛋”）的机会，你咋办？你还能说用二分法来测试么？ (难点一就告诉我们扔鸡蛋的次数很重要)，因此这道题并不是用折半查找来解决问题。

难点三：如果你$只有一次扔鸡蛋的机会(鸡蛋数不限制)$，你能最多确定的最多楼层数是多少？
假设我们选择第一层扔鸡蛋，如果鸡蛋碎了，则F == 0，否则鸡蛋没有碎，则F == 1。根据结果发现，扔在第一楼，这一楼就可以确定是不是F。这时和鸡蛋的数量没有关系，因为扔了这一次，你已经没有扔的机会。
假设我们选择其他楼层x（x > 1），如果鸡蛋碎了，则F < x，如果鸡蛋没有碎，则F >= x。接下来呢？游戏结束了！！！你只有一次扔鸡蛋的机会！！！
所以如果你只有一次扔鸡蛋的机会，这时你只能在第一层扔鸡蛋，这样你就能确定一层是否是F。

它还告诉我们，如果你有N次测试机会，哪怕你只有一个鸡蛋，你也可以找出任意的F，你从第一层测试，逐渐往上测试，并且会确定F。

难点四：经过若干次扔鸡蛋，你已经确定了[0, h]都没有碎，则F >= h，不确定的楼层为[h, N]。这时我们采用上面的策略，在第h + 1层扔鸡蛋（注意不是第h层，第h层已经知道了不会碎），如果鸡蛋碎了则F = h，否则鸡蛋没有碎，F > h，这时你又确定了F不在第h层，所以增加了一层。

如果你有remainTestCount个测试机会（扔鸡蛋的机会 或者移动的次数），eggsCount个鸡蛋，这时我们任意选择在第x层扔鸡蛋，如果鸡蛋没碎，这时你还剩余remainTestCount - 1次机会，eggsCount个鸡蛋，我们可以确定x下面的getConfirmFloors(remainTestCount - 1, eggsCount) 层
如果鸡蛋碎了，这时你还剩余remainTestCount - 1次机会，eggsCount - 1个鸡蛋，我们可以确定getConfirmFloors(remainTestCount - 1, eggsCount - 1)层，并且x层也被确定了
因此可以得出规律：

getConfirmFloors(remainTestCount, eggsCount) = getConfirmFloors(remainTestCount - 1, eggsCount) + getConfirmFloors(remainTestCount - 1, eggsCount - 1) + 1

其中getConfirmFloors(remainTestCount, eggsCount) 表示的是在remainTestCount个测试机会（扔鸡蛋的机会 或者移动的次数），eggsCount个鸡蛋可以确定的楼层数量

class Solution {
public:
    int superEggDrop(int K, int N) {
        int remainTestCount = 1;//穷举移动次数（测试的次数）
        while (getConfirmFloors(remainTestCount, K) < N){
            ++remainTestCount;
        }
        return remainTestCount;
    }
    //在remainTestCount个测试机会（扔鸡蛋的机会 或者移动的次数），eggsCount个鸡蛋可以确定的楼层数量
    int getConfirmFloors(int remainTestCount, int eggsCount){
        if (remainTestCount == 1 || eggsCount == 1){（难点三、四）
            //如果remainTestCount == 1你只能移动一次，则你只能确定第一楼是否，也就是说鸡蛋只能放在第一楼，如果碎了，则F == 0，如果鸡蛋没碎，则F == 1
            //如果eggsCount == 1鸡蛋数为1，它碎了你就没有鸡蛋了，为了保险，你只能从第一楼开始逐渐往上测试，如果第一楼碎了（同上），第一楼没碎继续测第i楼，蛋式你不可能无限制的测试，因为你只能测试remainTestCount次
            return remainTestCount;
        }
        return getConfirmFloors(remainTestCount - 1, eggsCount - 1) + 1 + getConfirmFloors(remainTestCount - 1, eggsCount);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19