• 程式範例: C++
• 難度: ⭐⭐⭐⭐⭐
• 觀念：思維、二分搜、動態規劃、數學

# 著名的雞蛋掉落問題

我有雞蛋$K$ 個，有一棟樓共有$N$ 層，現在我從任意一層開始扔雞蛋，雞蛋可能會碎，可能不會；如果沒有碎，我可以撿起來繼續扔，現在想找到一個臨界樓層，從這個樓層以及該樓層以下往下扔，雞蛋都不會碎，從這個樓層以上往下扔，雞蛋都會碎。

# 基本思考

# 解決思路

# 動態規劃 + 二分搜

定義$dp[K][N]$ 為有$K$ 個雞蛋，$N$ 層樓情況下，找到臨界樓層至少要扔雞蛋的次數。
考慮狀態轉移方程，假設從 x 層開始扔第一個雞蛋，有兩種情況：

1. 雞蛋碎了，說明臨界樓層在$1$~$x-1$ 之間，且雞蛋碎了一個，因此情況轉變為$dp[K-1][x-1]$
2. 雞蛋沒有碎，說明臨界樓層在$x$~$N$ 之間，且雞蛋可以撿起來繼續扔，因此情況變為$dp[K][N-x]$

需要考慮最壞情況，因此得取這兩個情況的的最大值，再加上當前從 x 扔的這次，狀態轉移方程如下：
$dp[K][N]=max(dp[K-1][x],dp[K][N-x])+1$
但是第一枚雞蛋從$x$ 層開始扔是我們假設的，第一枚雞蛋從哪一層開始扔會使得所需的次數最小呢？
這裡就需要我們進行枚舉了，$1 \le x \le N$, 因此對狀態轉移方程進行改進：

$dp[K][N]=min_{1\le x \le N} (max (dp[K-1][x-1],dp[K][N-x])+1)$

此時，直接撰寫程式的話，$dp$ 的複雜度是$O(kn^2)$，共有一個$O(kn)$ 個狀態，對於每個狀態枚舉雞蛋的樓層$x$ 需要$O(n)$ 的時間。因此我們需要想辦法優化枚舉的時間複雜度。

我們觀察到$dp(k,n)$ 是一個對於$n$ 的單調函數，也就是說在雞蛋數$k$ 固定的情況下，樓層數$n$ 越多，需要的測量次數一定不會變少。在上述的轉移方程中，第一項$T_1(x) = dp(k-1,x-1)$ 是一個隨$x$ 增加的單調遞增函數，第二項$T_2(x) = dp(k,n-x)$ 是一個隨$x$ 增加而單調遞減的函數。

如果這兩個函數都是連續函數，那麼我們只需要找出這兩個函數的交點，在交點處就能保證這兩個函數的最大值最小。但在本題中，$T_1$ 和$T_2$ 都是離散函數。在這種情況下，我們需要找到最大的滿足$T_1(x) < T_2(x)$ 的$x_0$，以及最小的滿足$T_1(x) \ge T_2(x)$ 的$x_1$。

我們只需要比較在$x_0$ 和$x_1$ 處兩個函數的最大值，取一個最小的作為$x$ 即可。在數學上，我們可以證明出 $x_0$ 和$x_1$ 相差 1，這也是比較顯然的，因為它們正好夾住了那個想像中的交點，並且相距盡可能地近。因此我們就可以使用二分搜的方法找出$x_0$，再得到$x_1$：

• 我們在所有滿足條件的$x$ 上進行二分搜。對於狀態$(k,n)$ 而言，$x$ 即為$[1,n]$ 中的任一整數；

• 在二分搜的過程中，假設當前這一步我們查找到了$x_{mid}$，如果$T_1(x_{mid})>T_2(x_{mid})$，那麼真正的$x_0$ 一定在$x_{mid}$ 的左側，否則真正的 $x_0$ 就會在 $x_{mid}$ 的右側。

在得到了​$x_0$ 後，我們可以知道$x_1$​即為$x_0+1$ ，此時我們只需要比較 $max(T_1(x_0),T_2(x_0))$ 和$max(T_1(x_1),T_2(x_1))$，取較小的那個對應的位置作為 $x$ 即可。

這樣一來，對於給定的狀態$(k,n)$，我們只需要$O(log n)$ 的時間，就可以找到最優的$x$，因此，總時間複雜度從$O(kn^2)$ 就能降低至$O(knlog n)$ 了。

class Solution {

    unordered_map<int, int> memo;

    int dp(int k, int n) {

        if (memo.find(n * 100 + k) == memo.end()) {

            int ans;

            if (n == 0) {

                ans = 0;

            } else if (k == 1) {

                ans = n;

            } else {

                int lo = 1, hi = n;

                while (lo + 1 < hi) {

                    int x = (lo + hi) / 2;

                    int t1 = dp(k - 1, x - 1);

                    int t2 = dp(k, n - x);

                    if (t1 < t2) {

                        lo = x;

                    } else if (t1 > t2) {

                        hi = x;

                    } else {

                        lo = hi = x;

                    }

                }

                ans = 1 + min(max(dp(k - 1, lo - 1), dp(k, n - lo)),

                                   max(dp(k - 1, hi - 1), dp(k, n - hi)));

            }

            memo[n * 100 + k] = ans;

        }

        return memo[n * 100 + k];

    }

public:

    int superEggDrop(int k, int n) {

        return dp(k, n);

    }

};

# 單調性的處理

我們固定 $k$，隨著 $n$ 的增加，對於狀態轉移方程中 $dp(k-1, x-1)$ 這一項，它的值是不變的，因為它和 $n$ 無關。
而對於狀態轉移方程中 $dp(k, n-x)$ 這一項，隨著 $n$ 的增加，它的值也會增加。從上面的方法中，我們知道 $dp(k-1,x-1)$ 隨著 $x$ 單調遞增，而 $dp(k, n-x)$ 隨著 $x$ 單調遞減，那麼當 $n$ 增加時，$dp(k,n-x)$ 對應的函數折線圖在每個整數點上都是增加的，因此在 $dp(k-1,x-1)$ 不變的情況下，$x_{opt}$ 是單調遞增的。

我們可以想像一條斜率為負的直線和一條斜率為正的直線，當斜率為負的直線（模擬 $dp(k, n-x)$）向上平移（模擬 $n$ 的增加）時，它和斜率為正的直線（模擬 $dp(k-1, x-1)$）的交點會一直向右移動，這個交點就確定了$x_{opt}$，這與方法一也是一致的。

因此當我們固定 $k$ 時，隨著 $n$ 的增加，$dp(k, n)$ 對應的最優解的坐標 $x_{opt}$ 單調遞增，這樣一來每個 $dp(k, n)$ 的均攤時間複雜度為 $O(1)$。

class Solution {

public:

    int superEggDrop(int k, int n) {

        int dp[n + 1];

        for (int i = 0; i <= n; ++i) {

            dp[i] = i;

        }

        for (int j = 2; j <= k; ++j) {

            int dp2[n + 1];

            int x = 1; 

            dp2[0] = 0;

            for (int m = 1; m <= n; ++m) {

                while (x < m && max(dp[x - 1], dp2[m - x]) >= max(dp[x], dp2[m - x - 1])) {

                    x++;

                }

                dp2[m] = 1 + max(dp[x - 1], dp2[m - x]);

            }

            for (int m = 1; m <= n; ++m) {

                dp[m] = dp2[m];

            }

        }

        return dp[n];

    }

};

# 數學的方法

反過來想這個問題：如果我們可以做 $t$ 次操作，而且有 $k$ 個雞蛋，那麼我們能找到答案的最高的 n 是多少？我們設 $f(t,k)$ 為在上述條件下的 $n$。如果我們求出了所有的$f(t,k)$，那麼只需要找出最小的滿足 $f(t, k) \ge n$ 的 $t$。

我們需要找出最高的 $n$，因此我們不必思考到底在哪裡扔這個雞蛋，我們只需要扔出一個雞蛋，看看到底發生了什麼：

• 如果雞蛋沒有碎，那麼對應的是$f(t-1,k)$，也就是說在這一層的上方可以有$f(t-1,k)$ 層；
• 如果雞蛋碎了，那麼對應的是$f(t-1,k-1)$，也就是說在這一層的下方可以有 $f(t-1,k-1)$ 層。

因此我們就可以寫出狀態轉移方程：
$f(t, k) = 1 + f(t-1, k-1) + f(t-1, k)$

邊界條件為：

• 當 $t \ge 1$ 的時候 $f(t, 1) = t$。
• 當 $k \ge 1$ 時，$f(1, k) = 1$。

class Solution {

public:

    int superEggDrop(int k, int n) {

        if (n == 1) {

            return 1;

        }

        vector<vector<int>> f(n + 1, vector<int>(k + 1));

        for (int i = 1; i <= k; ++i) {

            f[1][i] = 1;

        }

        int ans = -1;

        for (int i = 2; i <= n; ++i) {

            for (int j = 1; j <= k; ++j) {

                f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];

            }

            if (f[i][k] >= n) {

                ans = i;

                break;

            }

        }

        return ans;

    }

};