LeetCode 887. Super Egg Drop 超級雞蛋掉落

語言: CN / TW / HK

https://leetcode.com/problems/super-egg-drop/

Discuss: https://www.cnblogs.com/grandyang/p/11048142.html

You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Example 1:

Input: k = 1, n = 2 Output: 2 Explanation: Drop the egg from floor 1. If it breaks, we know that f = 0. Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1. If it does not break, then we know f = 2. Hence, we need at minimum 2 moves to determine with certainty what the value of f is.

Example 2:

Input: k = 2, n = 6 Output: 3

Example 3:

Input: k = 3, n = 14 Output: 4

Constraints:

  • 1 <= k <= 100
  • 1 <= n <= 104

解法一:

這道題說給了我們K個雞蛋,還有一棟共N層的大樓,說是雞蛋有個臨界點的層數F,高於這個層數扔雞蛋就會碎,否則就不會,問我們找到這個臨界點最小需要多少操作,注意這裡的操作只有當前還有沒碎的雞蛋才能進行。這道題是基於經典的扔雞蛋的問題改編的,原題是有 100 層樓,為了測雞蛋會碎的臨界點,最少可以扔幾次?答案是隻用扔 14 次就可以測出來了,講解可以參見油管上的這個影片,這兩道題看著很相似,其實是有不同的。這道題限制了雞蛋的個數K,假設我們只有1個雞蛋,碎了就不能再用了,這時我們要測 100 樓的臨界點的時候,只能一層一層去測,當某層雞蛋碎了之後,就知道臨界點了,所以最壞情況要測 100 次,注意要跟經典題目中扔 14 次要區分出來。那麼假如有兩個雞蛋呢,其實需要的次數跟經典題目中的一樣,都是 14 次,這是為啥呢?因為在經典題目中,我們是分別間隔 14,13,12,...,2,1,來扔雞蛋的,當我們有兩個雞蛋的時候,我們也可以這麼扔,第一個雞蛋仍在 14 樓,若碎了,說明臨界點一定在 14 樓以內,可以用第二個雞蛋去一層一層的測試,所以最多操作 14 次。若第一個雞蛋沒碎,則下一次扔在第 27 樓,假如碎了,說明臨界點在 (14,27] 範圍內,用第二個雞蛋去一層一層測,總次數最多 13 次。若第一個雞蛋還沒碎,則繼續按照 39, 50, ..., 95, 99,等層數去測,總次數也只可能越來越少,不會超過 14 次的。但是照這種思路分析的話,博主就不太清楚有3個雞蛋,在 100 樓測,最少的步驟數,答案是9次,博主不太會分析怎麼測的,各位看官大神知道的話一定要告訴博主啊。

其實這道題比較好的解法是用動態規劃 Dynamic Programming,因為這裡有兩個變數,雞蛋數K和樓層數N,所以就要使用一個二維陣列 DP,其中 dp[i][j] 表示有i個雞蛋,j層樓要測需要的最小運算元。那麼我們在任意k層扔雞蛋的時候就有兩種情況(注意這裡的k跟雞蛋總數K沒有任何關係,k的範圍是 [1, j]):

  • 雞蛋碎掉:接下來就要用 i-1 個雞蛋來測 k-1 層,所以需要 dp[i-1][k-1] 次操作。
  • 雞蛋沒碎:接下來還可以用i個雞蛋來測 j-k 層,所以需要 dp[i][j-k] 次操作。\ 因為我們每次都要面對最壞的情況,所以在第j層扔,需要 max(dp[i-1][k-1], dp[i][j-k])+1 步,狀態轉移方程為:

dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1) ( 1 <= k <= j )

程式碼如下: ```kotlin class Solution { fun superEggDrop(k: Int, n: Int): Int { val dp = Array(size = k + 1, init = { IntArray(size = n + 1, init = { 0 }) }) for (j in 1..n) { dp[1][j] = j }

    for (i in 2..k) {
        for (j in 1..n) {
            dp[i][j] = j
            for (kk in 1 until j) {
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][kk - 1], dp[i][j - k]) + 1)
            }
        }
    }
    return dp[k][n]
}

} ```

這種寫法會超時 Time Limit Exceeded,OJ 對時間卡的還是蠻嚴格的,所以我們就需要想辦法去優化時間複雜度。這種寫法裡面我們枚舉了 [1, j] 範圍所有的k值,總時間複雜度為 O(KN^2),若我們仔細觀察 dp[i - 1][k - 1] 和 dp[i][j - k],可以發現前者是隨著k遞增,後者是隨著k遞減,且每次變化的值最多為1,所以只要存在某個k值使得二者相等,那麼就能得到最優解,否則取最相近的兩個k值做比較,由於這種單調性,我們可以在 [1, j] 範圍內對k進行二分查詢,找到第一個使得 dp[i - 1][k - 1] 不小於 dp[i][j - k] 的k值,然後用這個k值去更新 dp[i][j] 即可,這樣時間複雜度就減少到了 O(KNlgN),其實也是險過,參見程式碼如下:

```kotlin class Solution { fun superEggDrop(k: Int, n: Int): Int { val dp = Array(size = k + 1, init = { IntArray(size = n + 1, init = { 0 }) }) for (j in 1..n) { dp[1][j] = j }

    for (i in 2..k) {
        for (j in 1..n) {
            dp[i][j] = j
            var left = 1
            var right = j

            while (left < right) {
                val mid = left + (right - left) / 2
                if (dp[i - 1][mid - 1] < dp[i][j - mid]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][right - 1], dp[i][j - right]) + 1)
        }
    }
    return dp[k][n]
}

} ```

解法二:

進一步來想,對於固定的k,dp[i][j-k] 會隨著j的增加而增加,最優決策點也會隨著j單調遞增,所以在每次移動j後,從上一次的最優決策點的位置來繼續向後查詢最優點即可,這樣時間複雜度就優化到了 O(KN),我們使用一個變數s表示當前的j值下的的最優決策點,然後當j值改變了,我們用一個 while 迴圈,來找到第下一個最優決策點s,使得 dp[i - 1][s - 1] 不小於 dp[i][j - s],參見程式碼如下: ```kotlin class Solution { fun superEggDrop(k: Int, n: Int): Int { val dp = Array(size = k + 1, init = { IntArray(size = n + 1, init = { 0 }) }) for (j in 1..n) { dp[1][j] = j }

    for (i in 2..k) {
        var s = 1
        for (j in 1..n) {
            dp[i][j] = j
            while (s < j && dp[i - 1][s - 1] < dp[i][j - s]) {
                s++
            }
            dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][s - 1], dp[i][j - s]) + 1)
        }
    }
    return dp[k][n]
}

} ```

解法三:

其實我們還可以進一步優化時間複雜度到 O(KlgN),不過就比較難想到了,需要將問題轉化一下,變成已知雞蛋個數,和操作次數,求最多能測多少層樓的臨界點。還是使用動態規劃 Dynamic Programming 來做,用一個二維 DP 陣列,其中 dp[i][j] 表示當有i次操作,且有j個雞蛋時能測出的最高的樓層數。再來考慮狀態轉移方程如何寫,由於 dp[i][j] 表示的是在第i次移動且使用第j個雞蛋測試第 dp[i-1][j-1]+1 層,因為上一個狀態是第i-1次移動,且用第j-1個雞蛋。此時還是有兩種情況:

  • 雞蛋碎掉:說明至少可以測到的不會碎的層數就是 dp[i-1][j-1]。
  • 雞蛋沒碎:那這個雞蛋可以繼續利用,此時我們還可以再向上查詢 dp[i-1][j] 層。

那麼加上當前層,總共可以通過i次操作和j個雞蛋查詢的層數範圍是 [0, dp[i-1][j-1] + dp[i-1][j] + 1],這樣就可以得到狀態轉移方程如下:

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1

當 dp[i][K] 正好小於N的時候,i就是我們要求的最小次數了,參見程式碼如下: ``` class Solution { fun superEggDrop(k: Int, n: Int): Int { val dp = Array(size = n + 1, init = { IntArray(size = k + 1, init = { 0 }) }) var m = 0

    while (dp[m][k] < n) {
        m++
        for (j in 1..k) {
            dp[m][j] = dp[m - 1][j - 1] + dp[m - 1][j] + 1
        }
    }
    return m
}

} ```

解法四:

我們可以進一步的優化空間,因為當前的操作次數值的更新只跟上一次操作次數有關,所以我們並不需要儲存所有的次數,可以使用一個一維陣列,其中 dp[i] 表示當前次數下使用i個雞蛋可以測出的最高樓層。狀態轉移方程的推導思路還是跟上面一樣,參見程式碼如下: c++ class Solution { public: int superEggDrop(int K, int N) { vector<int> dp(K + 1); int res = 0; for (; dp[K] < N; ++res) { for (int i = K; i > 0; --i) { dp[i] = dp[i] + dp[i - 1] + 1; } } return res; } };

解法五:

下面這種方法就非常的 tricky 了,居然推匯出了使用k個雞蛋,移動x次所能測的最大樓層數的通項公式,推導過程可以參見這個帖子,通項公式如下: f(k,x) = x(x-1)..(x-k)/k! + ... + x(x-1)(x-2)/3! + x(x-1)/2! + x 這數學功底也太好了吧,有了通向公式後,我們就可以通過二分搜尋法 Binary Search 來快速查詢滿足題目的x。這裡其實是博主之前總結貼 LeetCode Binary Search Summary 二分搜尋法小結 中的第四類,用子函式當作判斷關係,這裡子函式就是用來實現上面的通向公式的,不過要判斷,當累加和大於等於N的時候,就要把當的累加和返回,這樣相當於進行了剪枝,因為在二分法中只需要知道其跟N的大小關係,並不 care 到底大了多少,這樣快速定位x的方法執行速度貌似比上面的 DP 解法要快不少,但是這通項公式尼瑪誰能容易的推匯出來,只能膜拜歎服了,參見程式碼如下:

c++ class Solution { public: int superEggDrop(int K, int N) { int left = 1, right = N; while (left < right) { int mid = left + (right - left) / 2; if (helper(mid, K, N) < N) left = mid + 1; else right = mid; } return right; } int helper(int x, int K, int N) { int res = 0, r = 1; for (int i = 1; i <= K; ++i) { r *= x - i + 1; r /= i; res += r; if (res >= N) break; } return res; } };