問題：

? ? 假設有2個雞蛋和100層樓，將雞蛋從第n層扔下，雞蛋沒有碎，將雞蛋從n+1層扔下，雞蛋碎了，那么n層就是雞蛋不會摔碎的臨界點。

問：如何用最少的次數(shù)測試出最壞的情況下雞蛋不會摔破的臨界點。

思路一：二分法

? ? 對于均勻列表的查找，我們首先想到的是二分法。在本題中，首先第一個雞蛋從五十層扔，因為只有兩個雞蛋，假如第一個碎了，第二個不能在使用二分法，所以得從第一層開始一層層實驗。那么最壞的情況需要50次。

思路二：開平方

? ? 為了使次數(shù)最少，那么兩個雞蛋在最壞的情況下試的次數(shù)數(shù)應該盡可能接近因為是兩個雞蛋，很容易想到開平方100 = 10 * 10，第一個雞蛋從10，20···，這樣開始扔，那么最壞的情況是10，20，···，90，91，···，99，100共18次

思路三：逆推法

? ? 在思路二中，假設第一個雞蛋在第十層沒有碎，那么問題就變成了2個雞蛋從90層樓向下扔，求測出臨界點所需的最少次數(shù)，按照開平方的思路，應該對90開平方，依次類推，可以看出思路二也不是最優(yōu)解。為了找出最優(yōu)解，我們采用逆推法：

• 第一步：假定x是最優(yōu)解，然后找出第一次雞蛋應該扔下的樓層
• 第二步：假設我們從x+1層開始嘗試，那么最壞的情況是，雞蛋x+1層碎了，第二個雞蛋需要從第一層一直試到x層，共試了x+1次，這與最優(yōu)解x次矛盾。
• 第三步：假設我們從x-1層開始嘗試，那么最壞的情況是，雞蛋x-1層碎了，第二個雞蛋需要從第一層一直試到x-2層，共試了x-1次，這也與最優(yōu)解x次矛盾。
• 第四步：從二，三步來看，應該從x層開始扔，假設層雞蛋碎了，最壞嘗試次數(shù)為x，和假設相符合。
• 第五步：假設x層雞蛋沒碎，那么前x層被排除了，那么接下來問題轉(zhuǎn)換成了“從100-x層上扔2個雞蛋，用最少的次數(shù)測試出最壞的情況下雞蛋不會摔破的臨界點”，而該問題的最優(yōu)解是x-1，且應該從x+(x-1)層，開始測試。

• 第六步：以第五步類推，假設第一個雞蛋始終沒有碎，最后該開始測試的樓層是x+(x-1)+(x-2)+....+1，因為我們有100層樓，可以得到下面公式：

  
  
• 第七步：因為x是正整數(shù)，所以x=14。即最優(yōu)解是14。

思路四：動態(tài)規(guī)劃

? ? 假設從x層開始測試時，以f(100)表示100層中從x層開始扔雞蛋測試出臨界點所需最少次數(shù)，有以下情況：

• 雞蛋在x層碎了，最壞還需測試100-x次
• 雞蛋在x層未碎，最壞還需要f(x-1)次

? ? 也就是說從x層開始測試最壞的情況是max(100-x,f(x-1))有以下公式:

• 狀態(tài)轉(zhuǎn)移方程

  
  

• 邊界

  
  

? ? 根據(jù)上面公式編寫java代碼

private static int f() {
    int floor = 100;
    int[] temp = new int[floor];
    temp[0] = 1;
    temp[1] = 2;
    for (int i = 2; i < floor; i++) {
        temp[i] = 1 + Math.max(i - 1, temp[0]);
        for (int j = 2; j <= i; j++)
            temp[i] = Math.min(1 + Math.max(i - j, temp[j - 1]), temp[i]);
    }
    return temp[floor - 1];
}

擴展

? ? 假設有n個雞蛋和m層樓，求是雞蛋不會摔碎的臨界點。同樣假設從x層開始測試時，以f(m,n)表示m層中從x層開始扔雞蛋測試出臨界點所需最少次數(shù)，有以下情況：

• 雞蛋在x層碎了，最壞還需要f(m-x,n-1)次

• 雞蛋在x層未碎，最壞還需要f(x-1，n)次
  ? ? 也就是說從x層開始測試最壞的情況是max(f(m-x,n-1),f(x-1,n)),有以下公式:

• 狀態(tài)轉(zhuǎn)移方程

  
  

• 邊界

  
  

? ? 根據(jù)上面公式編寫java代碼

private static int f(int floor, int eggs) {
    int[][] temp = new int[floor+1][eggs+1];
    for (int i = 1; i <= floor; i++) {
        for (int j = 1; j <= eggs; j++) {
            if (1 == i) {
                //f(1,n) = 1
                temp[i][j] = 1;
            } else if (1 == j) {
                //f(m,1) = m
                temp[i][j] = i;
            } else {
                //f(m,n)=min(1+max(f(m-x,n-1),f(x-1,n)))
                temp[i][j] = 1 + Math.max(temp[i - 2][j - 1], temp[1][j]);
                for (int k = 2; k <= i; k++) {
                    temp[i][j] = Math.min(temp[i][j], 1 + Math.max(temp[i - k][j - 1], temp[k - 1][j]));
                }
            }
        }
    }
    return temp[floor][eggs];
}