描述

有一個n層的建筑。如果一個雞蛋從第k層及以上落下，它會碎掉。如果從低于這一層的任意層落下，都不會碎。
有m個雞蛋，用最壞的情況下實驗次數(shù)最少的方法去找到k, 返回最壞情況下所需的實驗次數(shù)。

樣例

給出 m = 2, n = 100 返回 14
給出 m = 2, n = 36 返回 8

思路
動態(tài)規(guī)劃+遞歸。用二元數(shù)組存儲某雞蛋某層所需的次數(shù)。迭代試扔第一個雞蛋，在某層扔。

1. 扔碎了即轉(zhuǎn)為雞蛋少一個，樓層少一層的子問題。
2. 沒扔碎即轉(zhuǎn)化為雞蛋沒有少樓層少為上半層那么多的子問題。

代碼

public class Solution {
    /**
     * @param m the number of eggs
     * @param n the umber of floors
     * @return the number of drops in the worst case
     */
    public int dropEggs2(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; ++i) {
            dp[i][1] = 1;
            dp[i][0] = 0;
        }
     
        for (int j = 1; j <= n; ++j)
            dp[1][j] = j;

        for (int i = 2; i <= m; ++i) {
            for (int j = 2; j <= n; ++j) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 1; k <= j; ++k) {
                    dp[i][j] = Math.min(dp[i][j],
                        1 + Math.max(dp[i - 1][k - 1], dp[i][j - k]));
                }
            }
        }

        return dp[m][n];
    }
}