Java實作 LeetCode 887 雞蛋掉落（動态規劃，谷歌面試題，藍橋杯真題）

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

一篇解釋的部落格

PS：

* 雞蛋掉落，谷歌面試題，藍橋杯第九屆JavaC組第十題，藍橋杯第九屆JavaB組第三題（經典dp）
 * 這題我印象十分深刻（/(ㄒoㄒ)/~~）
 * 有 K 個雞蛋，有 N 層樓，用最少的操作次數 F 檢查出雞蛋的品質。
 *
 * 思路：
 * 本題應該逆向思維，若你有 K 個雞蛋，你最多操作 F 次，求 N 最大值。
 *
 * dp[k][f] = dp[k][f-1] + dp[k-1][f-1] + 1;
 * 解釋：
 * 0.dp[k][f]：如果你還剩 k 個蛋，且隻能操作 f 次了，所能确定的樓層。
 * 1.dp[k][f-1]：蛋沒碎，是以該部分決定了所操作樓層的上面所能容納的樓層最大值
 * 2.dp[k-1][f-1]：蛋碎了，是以該部分決定了所操作樓層的下面所能容納的樓層最大值
 * 又因為第 f 次操作結果隻和第 f-1 次操作結果相關，是以可以隻用一維數組。
           

class Solution {
   
    public int superEggDrop(int K, int N) {
        int[] dp = new int[K + 1];
        int ans = 0;    // 操作的次數
        while (dp[K] < N){
            for (int i = K; i > 0; i--) // 從後往前計算
                dp[i] = dp[i] + dp[i-1] + 1;
            ans++;
        }
        return ans;
    }
 
}