點擊藍色「力扣加加」關注我喲
加個「星標」，帶你揭開算法的神秘面紗！
https://leetcode-cn.com/problems/super-egg-drop/
題目描述你將獲得 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 <= 1001 <= N <= 10000
前置知識思路本題也是 vivo 2020 年提前批的一個筆試題。時間一個小時，一共三道題，分別是本題，合併 k 個鍊表，以及種花問題。
這道題我在很早的時候做過，也寫了題解[2]。現在看來，思路沒有講清楚。沒有講當時的思考過程還原出來，導致大家看的不太明白。今天給大家帶來的是 887.super-egg-drop 題解的「重製版」。思路更清晰，講解更透徹，如果覺得有用，那就轉發在看支持一下？OK，我們來看下這道題吧。
這道題乍一看很複雜，我們不妨從幾個簡單的例子入手，嘗試打開思路。
假如有 2 個雞蛋，6 層樓。我們應該先從哪層樓開始扔呢？想了一會，沒有什麼好的辦法。我們來考慮使用暴力的手段。
（圖 1. 這種思路是不對的）
既然我不知道先從哪層樓開始扔是最優的，那我就依次模擬從第 1，第 2。。。第 6 層扔。每一層樓丟雞蛋，都有兩種可能，碎或者不碎。由於是最壞的情況，因此我們需要模擬兩種情況，並取兩種情況中的扔次數的較大值（較大值就是最壞情況）。 然後我們從六種扔法中選擇最少次數的即可。
（圖 2. 應該是這樣的）
而每一次選擇從第幾層樓扔之後，剩下的問題似乎是一個規模變小的同樣問題。嗯哼？遞歸？
為了方便描述，我將 f(i, j) 表示有 i 個雞蛋， j 層樓，在最壞情況下，最少的次數。
偽代碼：
def superEggDrop(K, N):
ans = N
# 暴力枚舉從第 i 層開始扔
for i in range(1, N + 1):
ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1))
return ans如上代碼：
self.superEggDrop(K - 1, i - 1) 指的是雞蛋破碎的情況，我們就只剩下 K - 1 個雞蛋， 並且 i - 1 個樓層需要 check。self.superEggDrop(K, N - i) + 1 指的是雞蛋沒有破碎的情況，我們仍然有 K 個雞蛋， 並且剩下 N - i 個樓層需要 check。接下來，我們增加兩行遞歸的終止條件，這道題就完成了。
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
if K == 1: return N
if N == 0 or N == 1: return N
ans = N
# 暴力枚舉從第 i 層開始扔
for i in range(1, N + 1):
ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1))
return ans可是如何這就結束的話，這道題也不能是 hard，而且這道題是公認難度較大的 hard 之一。
上面的代碼會 TLE，我們嘗試使用記憶化遞歸來試一下，看能不能 AC。
class Solution:
@lru_cache()
def superEggDrop(self, K: int, N: int) -> int:
if K == 1: return N
if N == 0 or N == 1: return N
ans = N
# 暴力枚舉從第 i 層開始扔
for i in range(1, N + 1):
ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1))
return ans性能比剛才稍微好一點，但是還是很容易掛。
那隻好 bottom-up（動態規劃）啦。
(圖 3)
我將上面的過程簡寫成如下形式：
(圖 4)
與其遞歸地進行這個過程，我們可以使用迭代的方式。相比於上面的遞歸式，減少了棧開銷。然而兩者有著很多的相似之處。
如果說遞歸是用函數調用來模擬所有情況， 那麼動態規劃就是用表來模擬。我們知道所有的情況，無非就是 N 和 K 的所有組合，我們怎麼去枚舉 K 和 N 的所有組合？當然是套兩層循環啦！
（圖 5. 遞歸 vs 迭代）
如上，你將 dp[i][j] 看成 superEggDrop(i, j)，是不是和遞歸是一摸一樣？
來看下迭代的代碼：
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
for i in range(K + 1):
for j in range(N + 1):
if i == 1:
dp[i][j] = j
if j == 1 or j == 0:
dp[i][j] == j
dp[i][j] = j
for k in range(1, j + 1):
dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1] + 1, dp[i][j - k] + 1))
return dp[K][N]值得注意的是，在這裡內外循環的順序無關緊要，並且內外循壞的順序對我們寫代碼來說複雜程度也是類似的，各位客官可以隨意調整內外循環的順序。比如這樣也是可以的：
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(N + 1):
for j in range( K + 1):
if j == 1:
dp[i][j] = i
if i == 1 or i == 0:
dp[i][j] == i
dp[i][j] = i
for k in range(1, i + 1):
dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1] + 1, dp[i - k][j] + 1))
return dp[N][K]
dp = [[0] * (N + 1) for _ in range(K + 1)]總結一下，上面的解題方法思路是：
然而這樣還是不能 AC。這正是這道題困難的地方。「一道題目往往有不止一種狀態轉移方程，而不同的狀態轉移方程往往性能是不同的。」
那麼這道題有沒有性能更好的其他的狀態轉移方程呢？
把思路逆轉！
❝這是《逆轉裁判》 中經典的臺詞， 主角在深處絕境的時候，會突然冒出這句話，從而逆轉思維，尋求突破口。
❞我們這樣來思考這個問題。既然題目要求最少的扔的次數，假設有一個函數 f(k, i)，他的功能是求出 k 個雞蛋，扔 i 次所能檢測的最高樓層。
我們只需要不斷進行發問：
」f 函數啊 f 函數，我扔一次可以麼？「， 也就是判斷 f(k, 1) >= N 的返回值」f 函數啊 f 函數，我扔兩次呢？「， 也就是判斷 f(k, 2) >= N 的返回值」f 函數啊 f 函數，我扔 m 次呢？「， 也就是判斷 f(k, m) >= N 的返回值我們只需要返回第一個返回值為 true 的 m 即可。
❝想到這裡，我條件發射地想到了二分法。聰明的小朋友們，你們覺得二分可以麼？為什麼？歡迎評論區留言討論。
❞那麼這個神奇的 f 函數怎麼實現呢？其實很簡單。
摔碎的情況，可以檢測的最高樓層是f(m - 1, k - 1) + 1。因為碎了嘛，我們多檢測了摔碎的這一層。沒有摔碎的情況，可以檢測的最高樓層是f(m - 1, k)。因為沒有碎，也就是說我們啥都沒檢測出來（對能檢測的最高樓層無貢獻）。我們來看下代碼：
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
def f(m, k):
if k == 0 or m == 0: return 0
return f(m - 1, k - 1) + 1 + f(m - 1, k)
m = 0
while f(m, K) < N:
m += 1
return m上面的代碼可以 AC。我們來順手優化成迭代式。
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for _ in range(N + 1)]
m = 0
while dp[m][K] < N:
m += 1
for i in range(1, K + 1):
dp[m][i] = dp[m - 1][i - 1] + 1 + dp[m - 1][i]
return m
代碼代碼支持：JavaSCript，Python
Python:
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for _ in range(N + 1)]
m = 0
while dp[m][K] < N:
m += 1
for i in range(1, K + 1):
dp[m][i] = dp[m - 1][i - 1] + 1 + dp[m - 1][i]
return mJavaSCript:
var superEggDrop = function (K, N) {
// 不選擇dp[K][M]的原因是dp[M][K]可以簡化操作
const dp = Array(N + 1)
.fill(0)
.map((_) => Array(K + 1).fill(0));
let m = 0;
while (dp[m][K] < N) {
m++;
for (let k = 1; k <= K; ++k) dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k];
}
return m;
};「複雜度分析」
時間複雜度：$O(m * K)$，其中 m 為答案。總結如果你還不熟悉動態規劃，可以先從遞歸做起。多畫圖，當你做多了題之後，就會越來越從容。對於動態規劃問題，往往有不止一種狀態轉移方程，而不同的狀態轉移方程往往性能是不同的。更多題解可以訪問我的 LeetCode 題解倉庫：https://github.com/azl397985856/leetcode 。目前已經 30K star 啦。
大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的 LeetCode 題解
Reference[1]動態規劃: https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md
[2]887.super-egg-drop 題解: https://github.com/azl397985856/leetcode/blob/master/problems/887.super-egg-drop.md