题目

k个鸡蛋从N楼层摔，如果确定刚好摔碎的那个楼层，最坏情况下最少要试验x次？

换个说法：

k个鸡蛋试验x次最多可以检测N层楼。计算出N？

逆向思维和数学公式解。

分析

定义N(k,x)

如果第k个鸡蛋碎了,则

还剩k-1块鸡蛋.

下一次只需检查下面的楼层.

还剩x-1次机会.

如果第k个鸡蛋没有碎,则

还剩k块鸡蛋.

下一次只需检查上面的楼层.

还剩x-1次机会.

即N(k,x) = 1 + N(k-1,x-1) + N(k,x-1)

初始值N(k,1)=1 N(1,x)=x

代码如下：

空间复杂度O(k)

时间复杂度O(k*lnN)

int solution(int n, int k) {
    int bs = log2n(n) + 1;
    if (k >= bs) {
        return bs;
    }
    int* dp = new int[k];
    for (int i = 0; i < k; i++) {
        dp[i] = 0;
    }    int r = 0;
    while (1) {
        r++;
        int p = 0;
        for (int i = 0; i < k; i++) {
            int tmp = dp[i];
            dp[i] += (p + 1);
            p = tmp;            if (dp[i] > n)
                return r;
        }
    }
}

数学公式解

当k确定，可以计算出N的公式解N(x)。

1. 级数求和。k越大，计算量越大。
2. 多项式拟合。计算量较小，比较简洁的方法。

可以算出结果：

k=1 N=x

k=2 N=(x2+x)/2

k=3 N=(x3+5x)/6

k=4 N=(x4-2x3+11x2+14x)/24