題目如下：
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?)
問(wèn)題一： 只有一個(gè)雞蛋的時(shí)候， 如何測(cè)試
如果我們只有一個(gè)雞蛋， 我們知道雞蛋一旦碎了， 我們就沒(méi)有雞蛋了。 所以我們要找出這個(gè)使得雞蛋恰好碎的critital floor樓層， 我們只能從第一層開(kāi)始向上一層一層的找。
所以最壞的情況下， 我們需要扔100次才能找到（即要么在100層， 要么在100層也不會(huì)碎）。-
問(wèn)題二： 現(xiàn)在我們有兩個(gè)雞蛋， 我們?cè)撊绾螠y(cè)試呢？
我們可以從第50層開(kāi)始扔， 這樣我們就可以把我們的問(wèn)題的規(guī)模減為一半了。 有兩種可能：
（1）蛋碎了， 我們知道critical floor在50層樓以下。 但是此時(shí)我們手里還剩下一只雞蛋， 我們沒(méi)有別的辦法， 只能從第一層開(kāi)始一層層的往上找。 最壞的情況下我們需要檢查： 1(對(duì)應(yīng)著第一個(gè)出師未捷的蛋) + 49 = 50次（2） 蛋沒(méi)有碎。 此時(shí)我們比較lucky， 然后繼續(xù)用這個(gè)蛋進(jìn)行二分測(cè)試。
無(wú)論如和， 我們?nèi)ド鲜鰞煞N情況最壞的情況， 即50次了。 問(wèn)題三： 能否做的更好
所以做的更好， 就是我們使得最壞情況下， 扔的次數(shù)是最小的。 我們可以選擇按照如下的方式扔雞蛋。
選擇10floor的strategy。 也就是選擇第一只雞蛋：先從10層開(kāi)始扔， 如果碎了， 就用第二個(gè)雞蛋check 1-9層。 如果沒(méi)有碎， 繼續(xù)用這一個(gè)雞蛋從20層開(kāi)始扔， 一直進(jìn)行下去。
最壞的情況下（即最大的扔雞蛋的次數(shù)）：
到90次的時(shí)候第一個(gè)雞蛋還沒(méi)有碎。 但是在100次的時(shí)候碎了。然后我們用第二個(gè)雞蛋測(cè)試從91層開(kāi)始， 一層層的測(cè)試。 我們的次數(shù)是： 10(第一個(gè)蛋) + 9 = 19次。
好的這個(gè)策略遠(yuǎn)好于第一個(gè)策略。問(wèn)題四： 還能做到更好嗎？
我們可以選擇minimization of maxmum regret的策略。
上述的辦法是采用的等差數(shù)列的方式扔雞蛋。 現(xiàn)在我們換個(gè)策略。 只要我們的第一個(gè)雞蛋不碎， 我們就減少增加的樓層數(shù)進(jìn)行扔雞蛋。 這樣就使得一旦我們的第一個(gè)雞蛋碎了， 那么使用第二個(gè)雞蛋測(cè)試所需要的次數(shù)的是遞減的。 例如第一個(gè)雞蛋在第一層就碎了與第一個(gè)雞蛋在第二層碎了這兩種可能對(duì)應(yīng)的導(dǎo)致的第二個(gè)雞蛋的測(cè)試次數(shù)是遞減的。
如何找到第一個(gè)雞蛋最開(kāi)始的扔雞蛋的層數(shù)。 我們按照如下方式計(jì)算出來(lái)：
（1）第一個(gè)雞蛋從樓層n開(kāi)始向下扔， 如果碎了， 使用第二個(gè)雞蛋一層層檢查前面(n-1)層樓。
（2）如果第一個(gè)雞蛋沒(méi)有碎， 那么接下來(lái)， 我們從2n - 1層開(kāi)始往下扔。 也就是說(shuō)此時(shí)我們又向上走了n -1層開(kāi)始扔第一個(gè)雞蛋。 如果碎了， 用第二個(gè)雞蛋檢查前面n -1 層。 沒(méi)有碎， 繼續(xù)向下扔第一個(gè)雞蛋。。
（3）第一個(gè)雞蛋沒(méi)有碎， 在樓層n + n - 1 + n -2 = 3n -3處扔雞蛋。
依次進(jìn)行下去。
我們有如下公式：
n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100
于是得到：
n (n+1) / 2 >= 100
計(jì)算得到：
n = 13.651。
我們?nèi)eiling， 得到n = 14.
所以我們測(cè)試的情況如下：
最壞的情況是我們?nèi)恿?4次。 也就是我們第一次扔第一個(gè)蛋的時(shí)候， 這個(gè)悲催的家伙就碎了。 然后我們只能從一層開(kāi)始向上， 逐層的用第二個(gè)蛋檢查：
1 + 13 = 14。
下面我們使用動(dòng)態(tài)規(guī)劃求解這個(gè)題。
n個(gè)雞蛋， k層樓。
一個(gè)問(wèn)題要想搭上動(dòng)態(tài)規(guī)劃這趟高速列車(chē)， 那么這個(gè)問(wèn)題的結(jié)構(gòu)必須擁有如下兩個(gè)優(yōu)秀的特點(diǎn)。
（1）最優(yōu)子結(jié)構(gòu)
如果雞蛋從x層向下扔的時(shí)候，會(huì)出現(xiàn)兩個(gè)case:
– case 1: 雞蛋碎了， 此時(shí)我們需要使用剩下的雞蛋n - 1（假如我們有n 個(gè)雞蛋）個(gè)雞蛋去檢查下面的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） 重疊子問(wèn)題
這個(gè)很容易看出來(lái)。
算法思路圖：
遞歸版本的編程實(shí)現(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;
}
需要注意的是，遞歸的效率特別慢，我們需要記住一句話，就是：
任何遞歸都可以用迭代去替換
這里要怎么用迭代去替換遞歸，我還在思考當(dāng)中。。。
