前段時間嘗試開始寫了一波簡書，被我的小伙伴嘲笑了一波，說我寫的沒有什么難度，讓我來一道摔雞蛋，今天剛好有空，接受他的挑戰(zhàn)直接來一道困難的雞蛋掉落問題。題目如下：
題目鏈接https://leetcode-cn.com/problems/super-egg-drop/
你將獲得K個雞蛋，并可以使用一棟從1到N共有?N層樓的建筑。
每個蛋的功能都是一樣的，如果一個蛋碎了，你就不能再把它掉下去。
你知道存在樓層F?，滿足0 <= F <= N?任何從高于?F的樓層落下的雞蛋都會碎，從F樓層或比它低的樓層落下的雞蛋都不會破。
每次移動，你可以取一個雞蛋（如果你有完整的雞蛋）并把它從任一樓層X扔下（滿足1 <= X <= N）。
你的目標(biāo)是確切地知道?F?的值是多少。
無論?F?的初始值如何，你確定?F?的值的最小移動次數(shù)是多少？
示例 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
思路：
這題目第一眼看下去確實沒有很大的思路，題目大概意思是說給你有限個雞蛋（雞蛋摔壞了就沒了），然后讓你在一個N層樓高的樓層去摔，用最少的次數(shù)找到雞蛋在那一層才會被摔碎。
那我們先來屢一下思路，往簡單點想：
假如我們有無限個雞蛋，有100層樓高，是不是就像猜數(shù)字一樣，在1-100里面猜數(shù)字，沒有猜對，主持人會告訴你大了還是小了的游戲（碎了就是大了，沒碎就是小了），那我們肯定無腦選擇中間值去摔，先在50層摔，如果碎了，就在1-49層去再找中間值摔，如果沒碎，就去51-100層找中間值摔。每次折半，我們需要log（100）次也就是7次。
假如我們只有一個雞蛋，有100層樓高，我們還能不能像剛才那樣從50層開始摔呢？很明顯是不能，因為一旦我們從50層開始摔，萬一雞蛋碎了，后面我們就沒有雞蛋可以去摔了，我們承擔(dān)不起雞蛋被摔碎了的風(fēng)險，所以如果只有1個雞蛋，我們被迫只能腳踏實地從第一層開始摔，如果沒有碎，再一層一層往上摔。如果雞蛋在100層才碎，我們最終將會摔100次，所以我們需要的次數(shù)就是100次。
那假如我們有兩個雞蛋，有100層樓高，這就不一樣了，我們有了基本，可以從高一點的樓層摔，如果摔碎了，我們還有一個雞蛋可以再一層一層摔，但是這就有個問題了，從高一點的樓層摔是多高呢？如果從50層摔，碎了，我們要再摔50次，沒碎我們就相當(dāng)于從51-100層摔2個雞蛋，具體的次數(shù)等同于我們有兩個雞蛋，有50層樓高的這樣一種情況，肯定是低于50次的，但是按照總次數(shù)來說肯定還是選擇最壞情況50次，那么這是不是最優(yōu)解呢？會不會從33層摔下去，次數(shù)更低呢？
當(dāng)想到這里，很容易的看出來，當(dāng)碎了和沒碎的情況所需要的次數(shù)相等時（或者是最接近時），次數(shù)更低。那么也就是說我們想要知道從那一層開始摔是最好的，必須一層一層遍歷去判斷。當(dāng)我們遍歷到第10層時，碎了的情況的次數(shù)就等同于（我們只有一個雞蛋【這里考了一道小學(xué)數(shù)學(xué)題：兩個雞蛋碎了一個還有多少個？】，有9層樓高），沒碎的情況就等同于（我們有兩個雞蛋【這里又考了一道小學(xué)數(shù)學(xué)題：兩個雞蛋摔了一個沒碎還有多少個？】，有90層樓高）。當(dāng)分析到這里，我們要求有兩個雞蛋，有100層樓高的情況，就需要知道一個雞蛋9層樓和兩個雞蛋90層樓的解，也就是原題目子問題的解，很明顯的動態(tài)規(guī)劃的思路。
解析：
使用DP去實現(xiàn)，按照題目意思定義一個dp[105][10005]數(shù)組，dp[x][y]代表x個雞蛋y層樓的最優(yōu)解。初始化為0。
把x=1的全賦值為y代表只有一個雞蛋的情況下，最優(yōu)解為樓層數(shù)。
然后從x=2開始動態(tài)規(guī)劃求解每一個子問題的最優(yōu)解。
代碼如下：
class Solution {
public:
int dp[105][10005] = { 0 };
int superEggDrop(int K, int N) {
if (K == 1) return N;
if (dp[K][N]) return dp[K][N];
for (int y = 1; y <= N; ++y) dp[1][y] = y;
for (int x = 2; x <= K; ++x)
{
for (int y = 1; y <= N; ++y)
{
int minNUM = y;
for (int i = 1; i <= y; ++i)
{
int temp = std::max(dp[x - 1][i - 1], dp[x][y - i]) + 1;
if (temp < minNUM) minNUM = temp;
}
dp[x][y] = minNUM;
}
}
return dp[K][N];
}
};
優(yōu)化：
通過了所有樣例，但是超時，這是在意料之中，K=100，N=10000這么大的數(shù)據(jù)規(guī)模，每一個子問題的解都要遍歷N遍，時間復(fù)雜度為O(K*N*N)，高達(dá)10^10。
那么要怎么優(yōu)化呢？如果要使用動態(tài)規(guī)劃的話，K*N的子問題是無可避免的，我們只能去優(yōu)化求解每個子問題的時間。
剛才我們每次求解子問題都是從i=1遍歷到i=N，那么在這個遍歷過程中，碎了的情況一開始肯定是最小的1次，逐步變大到N次。同時沒碎的情況的次數(shù)肯定是從大到小的一個過程。在這樣有規(guī)律的情況下，我們可以使用二分去優(yōu)化。
優(yōu)化后代碼如下：
class Solution {
public:
int dp[105][10005] = { 0 };
int superEggDrop(int K, int N) {
if (K == 1) return N;
if (dp[K][N]) return dp[K][N];
for (int y = 1; y <= N; ++y) dp[1][y] = y;
for (int x = 2; x <= K; ++x)
{
for (int y = 1; y <= N; ++y)
{
int minNUM = y;
int i = 1;
int j = y;
while (i <= j)
{
int m = i + ((j - i) >> 1);
int broken = dp[x - 1][m - 1];
int enbroken = dp[x][y - m];
int temp = std::max(broken,enbroken) + 1;
if (temp < minNUM) minNUM = temp;
if (broken < enbroken) i = m + 1;
else j = m - 1;
}
dp[x][y] = minNUM;
}
}
return dp[K][N];
}
};
雖然通過了，但是在速度上只擊敗了6%的用戶，說明還有更快的方法。
計算可知動態(tài)規(guī)劃加二分優(yōu)化的時間復(fù)雜度為O(K*N*logN)
