扔鸡蛋问题.md

dp[k][m] 表示 k 个鸡蛋，扔 m 次，最多能覆盖的楼层。 递推公式： dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1; 假设在 m 层扔了，dp[k][m - 1]表示鸡蛋没碎，则从该楼层往上；dp[k - 1][m - 1]表示鸡蛋碎了，则从该楼层往下。不管怎么样，都用了一次扔的机会，所以 m-1。而且这次扔，肯定能覆盖一层，所以最后+1。 整体 dp[k][m] 能覆盖的楼层，则是这三种情况之和。

    public int dropEggs(int Keggs, int Nfloor) {
        if (Keggs < 1 || Nfloor < 1) {
            return 0;
        }
        int bsTimes = log2N(Nfloor) + 1;
        if (Keggs >= bsTimes) {
            return bsTimes;
        }
        if (Keggs == 1) {
            return Nfloor;
        }
        int[][] dp = new int[Keggs + 1][Nfloor + 1];

        for (int m = 1; m <= Nfloor; m++) {
            for (int k = 1; k <= Keggs; k++) {
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;

            }
            // 返回条件
            if (dp[Keggs][m] >= Nfloor) {
                return m;
            }
        }
        return -1;

    }

    int log2N(int n) {
        int res = -1;
        while (n != 0) {
            res++;
            n = n >>> 1;
        }
        return res;

    }