題目如下：
You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that is it for that egg.
If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.
The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)
問題一： 只有一個雞蛋的時候值朋， 如何測試
如果我們只有一個雞蛋瘾英， 我們知道雞蛋一旦碎了关串， 我們就沒有雞蛋了。 所以我們要找出這個使得雞蛋恰好碎的critital floor樓層茄袖， 我們只能從第一層開始向上一層一層的找访雪。
所以最壞的情況下九秀， 我們需要扔100次才能找到（即要么在100層遗嗽， 要么在100層也不會碎）。-
問題二： 現(xiàn)在我們有兩個雞蛋鼓蜒， 我們該如何測試呢痹换？
我們可以從第50層開始扔征字， 這樣我們就可以把我們的問題的規(guī)模減為一半了。 有兩種可能：
（1）蛋碎了娇豫， 我們知道critical floor在50層樓以下匙姜。 但是此時我們手里還剩下一只雞蛋， 我們沒有別的辦法冯痢， 只能從第一層開始一層層的往上找氮昧。 最壞的情況下我們需要檢查： 1(對應(yīng)著第一個出師未捷的蛋) + 49 = 50次（2） 蛋沒有碎。 此時我們比較lucky系羞， 然后繼續(xù)用這個蛋進行二分測試。
無論如和霸琴， 我們?nèi)ド鲜鰞煞N情況最壞的情況椒振， 即50次了。 問題三： 能否做的更好
所以做的更好梧乘， 就是我們使得最壞情況下澎迎， 扔的次數(shù)是最小的。 我們可以選擇按照如下的方式扔雞蛋选调。
選擇10floor的strategy夹供。 也就是選擇第一只雞蛋：先從10層開始扔， 如果碎了仁堪， 就用第二個雞蛋check 1-9層哮洽。 如果沒有碎， 繼續(xù)用這一個雞蛋從20層開始扔弦聂， 一直進行下去鸟辅。
最壞的情況下（即最大的扔雞蛋的次數(shù)）：
到90次的時候第一個雞蛋還沒有碎。 但是在100次的時候碎了莺葫。然后我們用第二個雞蛋測試從91層開始匪凉， 一層層的測試。 我們的次數(shù)是： 10(第一個蛋) + 9 = 19次捺檬。
好的這個策略遠好于第一個策略再层。問題四： 還能做到更好嗎？
我們可以選擇minimization of maxmum regret的策略堡纬。
上述的辦法是采用的等差數(shù)列的方式扔雞蛋聂受。 現(xiàn)在我們換個策略。 只要我們的第一個雞蛋不碎烤镐， 我們就減少增加的樓層數(shù)進行扔雞蛋饺饭。 這樣就使得一旦我們的第一個雞蛋碎了， 那么使用第二個雞蛋測試所需要的次數(shù)的是遞減的职车。 例如第一個雞蛋在第一層就碎了與第一個雞蛋在第二層碎了這兩種可能對應(yīng)的導(dǎo)致的第二個雞蛋的測試次數(shù)是遞減的瘫俊。
如何找到第一個雞蛋最開始的扔雞蛋的層數(shù)鹊杖。 我們按照如下方式計算出來：
（1）第一個雞蛋從樓層n開始向下扔， 如果碎了扛芽， 使用第二個雞蛋一層層檢查前面(n-1)層樓骂蓖。
（2）如果第一個雞蛋沒有碎， 那么接下來川尖， 我們從2n - 1層開始往下扔登下。 也就是說此時我們又向上走了n -1層開始扔第一個雞蛋。 如果碎了叮喳， 用第二個雞蛋檢查前面n -1 層被芳。 沒有碎， 繼續(xù)向下扔第一個雞蛋馍悟。畔濒。
（3）第一個雞蛋沒有碎， 在樓層n + n - 1 + n -2 = 3n -3處扔雞蛋锣咒。
依次進行下去侵状。
我們有如下公式：
n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100
于是得到：
n (n+1) / 2 >= 100
計算得到：
n = 13.651。
我們?nèi)eiling毅整， 得到n = 14.
所以我們測試的情況如下：
最壞的情況是我們?nèi)恿?4次趣兄。 也就是我們第一次扔第一個蛋的時候， 這個悲催的家伙就碎了悼嫉。 然后我們只能從一層開始向上艇潭， 逐層的用第二個蛋檢查：
1 + 13 = 14。
下面我們使用動態(tài)規(guī)劃求解這個題戏蔑。
n個雞蛋暴区， k層樓。
一個問題要想搭上動態(tài)規(guī)劃這趟高速列車辛臊， 那么這個問題的結(jié)構(gòu)必須擁有如下兩個優(yōu)秀的特點仙粱。
（1）最優(yōu)子結(jié)構(gòu)
如果雞蛋從x層向下扔的時候，會出現(xiàn)兩個case:
– case 1: 雞蛋碎了彻舰， 此時我們需要使用剩下的雞蛋n - 1（假如我們有n 個雞蛋）個雞蛋去檢查下面的x - 1層樓伐割。
k ==> Number of floors
n ==> Number of Eggs
eggDrop(n, k) ==> Minimum number of trails needed to find the critical floor in worst case.
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): x in {1, 2, ..., k}}
（2） 重疊子問題
這個很容易看出來。
算法思路圖：
遞歸版本的編程實現(xiàn)：
static int max(int a, int b) => a > b ? a : b;
/// <summary>
/// Eggdrop the specified n and k.
/// </summary>
/// <returns>The eggdrop.</returns>
/// <param name="n">雞蛋數(shù)</param>
/// <param name="k">樓層數(shù)</param>
static int eggdrop(int n, int k)
{
if (n == 1)
{
return k;
}
if (k == 0||k==1)
{
return k;
}
int min = Int32.MaxValue;
int x, res;
for (x = 1; x <= k;x++)
{
res = max(eggdrop(n-1,x-1),eggdrop(n,k-x));
if(res<min){
min = res;
}
}
return min + 1;
}
需要注意的是刃唤，遞歸的效率特別慢隔心，我們需要記住一句話，就是：
任何遞歸都可以用迭代去替換
這里要怎么用迭代去替換遞歸尚胞，我還在思考當中硬霍。。笼裳。
