題目描述
你将獲得 K 個雞蛋，并可以使用一棟從 1 到 N 共有 N 層樓的建築。每次移動，你可以取一個雞蛋（如果你有完整的雞蛋）并把它從任一樓層 X 扔下（滿足 1 <= X <= N）。你知道存在樓層 F ，滿足 0 <= F <= N ，任何從高于 F 的樓層落下的雞蛋都會碎，從 F 樓層或比它低的樓層落下的雞蛋都不會破。你的目标是确切地知道 F 的值是多少。無論 F 的初始值如何，你确定 F 的值的最小移動次數是多少？（即最少扔幾次）
輸入：K = 1, N = 2
輸出：2
解釋：
雞蛋從 1 樓掉落。如果它碎了，我們肯定知道 F = 0 。
否則，雞蛋從 2 樓掉落。如果它碎了，我們肯定知道 F = 1 。
如果它沒碎，那麼我們肯定知道 F = 2 。
是以，在最壞的情況下我們需要移動 2 次以确定 F 是多少。
解題思路
這個題挺難的，面試還愛問。最直接的思路是線性掃描，但是這樣效率不高。實際上，如果本題不限制雞蛋個數的話，二分思路顯然可以得到最少嘗試的次數，但問題是，現在給你限制了雞蛋的個數
K
，直接使用二分思路就不行了（比如說隻給你
1
個雞蛋，
7
層樓，你敢用二分嗎？）。我的實作。
- 動态規劃：前文「不同定義有不同解法」就提過，找動态規劃的狀态轉移本就是見仁見智，比較玄學的事情，不同的狀态定義可以衍生出不同的解法，其解法和複雜程度都可能有巨大差異。這裡就是一個很好的例子。
- 如果根據“問什麼定義什麼”的思路，本題的狀态表示應該為：
這種定義方式效率比較低，會報逾時錯誤。具體解法和代碼請參照大佬題解和我的實作。# 用帶有兩個狀态參數的 dp 函數來表示狀态轉移 def dp(k, n) -> int # 目前狀态為 k 個雞蛋，面對 n 層樓 # 傳回這個狀态下最少的扔雞蛋次數 # 或用二維的 dp 數組表示的話也是一樣的 dp[k][n] = m # 目前狀态為 k 個雞蛋，面對 n 層樓 # 這個狀态下最少的扔雞蛋次數為 m -
重新定義狀态轉移：（狀态表示比較難了解，推薦記一下，這算是個很難的動态規劃題了）
現在，我們稍微修改下
dp
dp[k][m] = n # 目前有 k 個雞蛋，可以嘗試扔 m 次雞蛋 # 這個狀态下，最壞情況下最多能确切測試一棟 n 層的樓 # 比如說 dp[1][7] = 7 表示： # 現在有 1 個雞蛋，允許你扔 7 次; # 這個狀态下最多給你 7 層樓，使得你可以确定樓層 F 使得雞蛋恰好摔不碎 （一層一層線性探查嘛）這其實就是我們原始思路的一個**「反向」版本**，我們先不管這種思路的狀态轉移怎麼寫，先來思考一下這種定義之下，最終想求的答案是什麼？
我們最終要求的其實是扔雞蛋次數
m
m
dp
題目不是給你int superEggDrop(int K, int N) { int m = 0; while (dp[K][m] < N) { m++; // 狀态轉移... } return m; }K
N
m
while
dp[K][m] == N
K
m
N
層樓。
下面最重要的是要明确狀态轉移方程，有下面兩個事實：
- 無論你在哪層樓扔雞蛋（是以不需要窮舉樓層了），雞蛋隻可能摔碎或者沒摔碎（兩種可能），碎了的話就測樓下，沒碎的話就測樓上。
- 無論你上樓還是下樓，總的樓層數 = 樓上的樓層數 + 樓下的樓層數 + 1（目前這層樓）。
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1
dp[k][m - 1]
k
m
dp[k - 1][m - 1]
k-1
m
[LeetCode] 887、雞蛋掉落
- 如果根據“問什麼定義什麼”的思路，本題的狀态表示應該為：
參考代碼
解法一（會逾時）
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
memo = dict()
def dp(K, N) -> int:
# base case
if K == 1: return N
if N == 0: return 0
# 避免重複計算
if (K, N) in memo:
return memo[(K, N)]
res = float('INF')
# 窮舉所有可能的選擇
for i in range(1, N + 1):
res = min(res, max(dp(K, N - i), dp(K - 1, i - 1)) + 1)
# 記入備忘錄
memo[(K, N)] = res
return res
return dp(K, N)
解法二（可AC）
class Solution {
public:
int superEggDrop(int K, int N) {
// 定義dp[K+1][N+1]，m 最多不會超過 N 次（線性掃描）
vector<vector<int> > dp(K + 1, vector<int>(N + 1, 0));
// base case:
// dp[0][..] = 0
// dp[..][0] = 0
int m = 0;
while(dp[K][m] < N){
m++;
for(int k = 1; k <= K; k++)
dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1; // 碎 + 沒碎 + 1
}
return m;
}
};
優化成一維dp
/**
* 雞蛋掉落，鷹蛋（Leetcode 887）：（經典dp）
* 有 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 次操作結果相關，是以可以隻用一維數組。
*
* 時複：O(K*根号(N))
*/
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;
}
其中：
dp[2][3]
表示：