【問題描述】 [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來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/super-egg-drop 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

【解答思路】

李永樂老師的視頻：《復工復產找工作？先來看看這道面試題：雙蛋問題》

方法：動態規劃

1. 動態規劃 -超時

時間復雜度：O(N^3) 空間復雜度：O(N^2)

import java.util.Arrays;public class Solution {public int superEggDrop(int K, int N) {// dp[i][j]：一共有 i 層樓梯的情況下，使用 j 個雞蛋的最少實驗的次數// 注意：// 1、i 表示的是樓層的大小，不是第幾層的意思，例如樓層區間 [8, 9, 10] 的大小為 3，這一點是在狀態轉移的過程中調整的定義// 2、j 表示可以使用的雞蛋的個數，它是約束條件，我個人習慣放在后面的維度，表示消除后效性的意思// 0 個樓層和 0 個雞蛋的情況都需要算上去，雖然沒有實際的意義，但是作為遞推的起點，被其它狀態值所參考int[][] dp = new int[N + 1][K + 1];// 由于求的是最小值，因此初始化的時候賦值為一個較大的數，9999 或者 i 都可以for (int i = 0; i <= N; i++) {Arrays.fill(dp[i], i);}// 初始化：填寫下標為 0、1 的行和下標為 0、1 的列// 第 0 行：樓層為 0 的時候，不管雞蛋個數多少，都測試不出雞蛋的 F 值，故全為 0for (int j = 0; j <= K; j++) {dp[0][j] = 0;}// 第 1 行：樓層為 1 的時候，0 個雞蛋的時候，扔 0 次，1 個以及 1 個雞蛋以上只需要扔 1 次dp[1][0] = 0;for (int j = 1; j <= K; j++) {dp[1][j] = 1;}// 第 0 列：雞蛋個數為 0 的時候，不管樓層為多少，也測試不出雞蛋的 F 值，故全為 0// 第 1 列：雞蛋個數為 1 的時候，這是一種極端情況，要試出 F 值，最少次數就等于樓層高度（想想復雜度的定義）for (int i = 0; i <= N; i++) {dp[i][0] = 0;dp[i][1] = i;}// 從第 2 行，第 2 列開始填表for (int i = 2; i <= N; i++) {for (int j = 2; j <= K; j++) {for (int k = 1; k <= i; k++) {// 碎了，就需要往低層繼續扔：層數少 1 ，雞蛋也少 1// 不碎，就需要往高層繼續扔：層數是當前層到最高層的距離差，雞蛋數量不少// 兩種情況都做了一次嘗試，所以加 1dp[i][j] = Math.min(dp[i][j], Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1);}}}return dp[N][K];} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/super-egg-drop/solution/dong-tai-gui-hua-zhi-jie-shi-guan-fang-ti-jie-fang/

2. 優化

時間復雜度：O(N^2logN) 空間復雜度：O(N^2)

import java.util.Arrays;public class Solution {public int superEggDrop(int K, int N) {// dp[i][j]：一共有 i 層樓梯的情況下，使用 j 個雞蛋的最少仍的次數int[][] dp = new int[N + 1][K + 1];// 初始化for (int i = 0; i <= N; i++) {Arrays.fill(dp[i], i);}for (int j = 0; j <= K; j++) {dp[0][j] = 0;}dp[1][0] = 0;for (int j = 1; j <= K; j++) {dp[1][j] = 1;}for (int i = 0; i <= N; i++) {dp[i][0] = 0;dp[i][1] = i;}// 開始遞推for (int i = 2; i <= N; i++) {for (int j = 2; j <= K; j++) {// 在區間 [1, i] 里確定一個最優值int left = 1;int right = i;while (left < right) {// 找 dp[k - 1][j - 1] <= dp[i - mid][j] 的最大值 kint mid = left + (right - left + 1) / 2;int breakCount = dp[mid - 1][j - 1];int notBreakCount = dp[i - mid][j];if (breakCount > notBreakCount) {// 排除法（減治思想）寫對二分見第 35 題，先想什么時候不是解// 嚴格大于的時候一定不是解，此時 mid 一定不是解// 下一輪搜索區間是 [left, mid - 1]right = mid - 1;} else {// 這個區間一定是上一個區間的反面，即 [mid, right]// 注意這個時候取中間數要上取整，int mid = left + (right - left + 1) / 2;left = mid;}}// left 這個下標就是最優的 k 值，把它代入轉移方程 Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1) 即可dp[i][j] = Math.max(dp[left - 1][j - 1], dp[i - left][j]) + 1;}}return dp[N][K];} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/super-egg-drop/solution/dong-tai-gui-hua-zhi-jie-shi-guan-fang-ti-jie-fang/

【總結】

1.「動態規劃」的兩個思考方向：

1.自頂向下求解，稱之為「記憶化遞歸」：初學的時候，建議先寫「記憶化遞歸」的代碼，然后把代碼改成「自底向上」的「遞推」求解；
2.自底向上求解，稱之為「遞推」或者就叫「動態規劃」：在基礎的「動態規劃」問題里，絕大多數都可以從這個角度入手，做多了以后建議先從這個角度先思考，實在難以解決再考慮「記憶化遞歸」。

2. 「動態規劃」五步走

第 1 步：定義狀態
第 2 步：推導狀態轉移方程
第 3 步：考慮初始化
第 4 步：考慮輸出
第 5 步：思考狀態壓縮

3.二分查找優化

參考鏈接：https://leetcode-cn.com/problems/super-egg-drop/solution/dong-tai-gui-hua-zhi-jie-shi-guan-fang-ti-jie-fang/.

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第887题][鸡蛋掉落][谷歌面试][动态规划]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。