題目

k個雞蛋從N樓層摔，如果确定剛好摔碎的那個樓層，最壞情況下最少要試驗x次？

換個說法：

k個雞蛋試驗x次最多可以檢測N層樓。計算出N？

分析

定義N(k,x)

如果第k個雞蛋碎了,則

還剩k-1塊雞蛋.

下一次隻需檢查下面的樓層.

還剩x-1次機會.

如果第k個雞蛋沒有碎,則

還剩k塊雞蛋.

下一次隻需檢查上面的樓層.

即

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)。

級數求和。k越大，計算量越大。
多項式拟合。計算量較小，比較簡潔的方法。

可以算出結果：

k=1 N=x

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

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

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