點擊藍色「力扣加加」關注我喲
加個「星標」，帶你揭開算法的神秘面紗！
去年的一年時間，我在群裡每天都會出題給大家做。但是就在 2020-03 開始，力扣也開展了每日一題活動。我突然覺得這個每日一題的必要性變得小了很多，並且逐漸減少了出題頻率。但是我還是不願意放棄大家一起集中進行交流學習的機會。於是我打算新開闢一個專題，這個專題一方面要和力扣官方的每日一題重合度低，另一方面要讓大家有參與的熱情。
於是【異議！】系列應運而生。它是個什麼東西呢？我相信大家一定在平時刷算法的過程中，一定遇到過「這解法怎麼想到的？」，「這解法不對吧？」的情況，並且可悲的是沒有人能夠回答你。來這裡，「力扣加加」 來回答你。我們會對大家提出的問題進行篩選，將有意義的問題開放出來給大家討論和學習。
本次給大家帶來的/是【異議！】系列「第二彈」。
原題地址：https://leetcode-cn.com/problems/super-egg-drop/
事情的起源昨天有人在我的力扣題解下留言，問我《丟雞蛋問題》重製版來襲～》題解中為什麼第二種算法是加法而不是 min 什麼的。畢竟我的第一種算法可是 min(max(碎, 不碎))，為什麼第二種就是加法了呢？這個細節我在寫題解的時候漏掉了，我打算詳細給大家說一下。
題目描述你將獲得 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
我當時的解法我們這樣來思考這個問題。既然題目要求最少的扔的次數，假設有一個函數 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;
};「複雜度分析」
為什麼是加法在解法一種我提到了：「算法一的本質就是暴力地枚舉所有的可能樓層，然後比較最壞情況下的最少扔雞蛋次數」。而實際上解法二也是基於這個大前提，假設我們選擇一個樓層是 x。那麼在 x 層扔雞蛋會有兩種可能：
雞蛋碎了。說明目標樓層 F 就是本層或者比本層低，樓上的 N - x 層不需要檢測了，全部排除了。因此我們需要繼續探測樓下 x - 1 層，而我們剩下可以探測的最高樓層為 dp[k - 1][m - 1]。由於我們需要探測到具體的 F，因此我們需要使得 dp[k - 1][m - 1] >= x - 1。雞蛋沒碎。說明目標樓層 F 比本層高，樓下的 x - 1 不需要檢測了，全部排除了。因此我們需要繼續探測樓上 N - x 層，而我們剩下可以探測的最高樓層為 dp[k][m - 1]。由於我們需要探測到具體的 F，因此我們需要使得 dp[k][m - 1] >= N - x。❝無論雞蛋碎還是不碎，我們都只需要檢測上面或者檢測下面，不需要同時檢測。
❞也就是說我需要找到一個樓層 x， 使得 x 同時滿足：
dp[k - 1][m - 1] >= x - 1這樣能保證 100% 可以檢測出來目標樓層 F。實際上不管雞蛋碎不碎，可以檢測的樓層都是 「max(dp[k - 1][m - 1], x -1) + max(dp[k][m - 1], N -x) + 1」，由於 dp[k - 1][m - 1] >= x - 1，dp[k][m - 1] >= N - x，因此可以檢測的樓層就是 dp[k - 1][m - 1] + dp[k][m - 1] + 1。
這個我可能需要解釋一下。由於「選擇 x 開始扔之前已經確定了上面的兩個不等式是成立的了」，因此如果雞蛋沒碎，我們需要繼續往上檢測，下面是不需要檢測的，雖然下面是 x - 1，但是為了保證萬一碎的情況也有解，所以有 dp[k - 1][m - 1] >= x - 1，因此實際上可以確定的最大樓層是 dp[k][m - 1] + max(dp[k - 1][m - 1], x -1) + 1，也就是 dp[k][m - 1] + dp[k - 1][m - 1] + 1。雞蛋如果碎的情況也是一樣的分析邏輯。
大家對這道題還有任何問題，都可以留言告訴我！
1、力扣刷題插件
2、提前批算法工程師面試之路
3、動態規劃問題為什麼要畫表格？
4、《丟雞蛋問題》重製版來襲～
5、leetcode 刷500道題，筆試/面試穩嗎？談談算法的學習