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 是多少。
           

示例 2：

輸入：K = 2, N = 6
輸出：3
           

示例 3：

輸入：K = 3, N = 14
輸出：4
           

提示：

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

思 路 分 析 ： \color{blue}思路分析： 思路分析：這道題就是非常繞，讓人感覺好像答案隻與雞蛋的數量有關系。但這答題遇到了老衲，老衲定要解開它的真面目。話不多說，開始解題。

難點一：這道題的“移動”是不受空間限制的，我們潛意識裡可能會認為它是爬樓的次數，

認為在上次扔雞蛋的位置進行爬樓轉移到下一個位置所移動樓層的數目。

蛋式題目并不是這個意思，題幹說“每次移動，把它從任一樓層 X 扔下”，也就是說 你 可 以 測 試 多 少 次 或 者 說 你 可 以 仍 多 少 次 雞 蛋 \color{red}你可以測試多少次或者說你可以仍多少次雞蛋 你可以測試多少次或者說你可以仍多少次雞蛋。

難點二：對于折半查找數的遊戲大家都應該知道，是以對于[1, 2,3,4 …, N]這些樓層，我們使用折半查找的思路先在(N + 1) / 2這一樓層丢雞蛋，判斷是否破碎。

如果雞蛋碎了，則F在[1, (N + 1) / 2 - 1]，否則雞蛋沒有碎，F在[(N + 1) / 2, N]。

這樣給人的感覺就是隻和雞蛋的數量有關，如果雞蛋夠，使用二分法來測試，則必定會測試出F，如果雞蛋不夠。

蛋式你有沒有想過，如果你有無數個雞蛋，蛋我隻給你1次移動（“扔雞蛋”）的機會，你咋辦？你還能說用二分法來測試麼？ (難點一就告訴我們扔雞蛋的次數很重要)，是以這道題并不是用折半查找來解決問題。

難點三：如果你 隻 有 一 次 扔 雞 蛋 的 機 會 ( 雞 蛋 數 不 限 制 ) \color{red}隻有一次扔雞蛋的機會(雞蛋數不限制) 隻有一次扔雞蛋的機會(雞蛋數不限制)，你能最多确定的最多樓層數是多少？

假設我們選擇第一層扔雞蛋，如果雞蛋碎了，則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);
    }
};