leetcode_887_雞蛋掉落

參考連結1：https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/gao-lou-reng-ji-dan-wen-ti

參考連結2：https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/gao-lou-reng-ji-dan-jin-jie

參考連結3：https://leetcode-cn.com/problems/super-egg-drop/solution/zhi-xing-yong-shi-0-ms-zai-suo-you-java-ti-jia-121/

解法一：遞歸版    動态規劃+備忘錄+二分優化

函數dp(K,N)表示此時有K個雞蛋，樓層有N層需要測試多少次。

base case:

K==1時，即手中隻有一個雞蛋，需要測試N次

N==0時，即處于0層，需要測試0次

在第i層樓扔了雞蛋之後會出現雞蛋碎了和雞蛋沒碎兩種情況。

如果雞蛋碎了，那麼雞蛋的個數

K

應該減一，搜尋的樓層區間應該從

[1..N]

變為

[1..i-1]

共

i-1

層樓；

如果雞蛋沒碎，那麼雞蛋的個數

K

不變，搜尋的樓層區間應該從

[1..N]

變為

[i+1..N]

共

N-i

層樓。

因為我們要求的是最壞情況下扔雞蛋的次數，是以雞蛋在第

i

層樓碎沒碎，取決于那種情況的結果更大：

是以下面求res（最壞情況下的最少扔雞蛋次數）時，因該先對dp(K-1,i-1)和dp(K,N-i)求一下最大值然後加1再與res比較求最小值。

二分優化是因為：

dp(K-1,i-1)單調遞增，dp(K,N-i)單調遞減（具體為什麼看參考連結1，作者寫得很清楚），利用二分求這倆函數的交點

下面代碼中，帶注釋的是沒用二分優化求res的代碼，也能通過。二分優化的代碼沒注釋掉。

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo=dict()
        def dp(K,N)->int :
            if(K==1):return N
            if(N==0):return 0

            if(K,N) in memo:
                return memo[(K,N)]
            res=float('INF')
            #for i in range(1,N+1):
             #   res=min(res,
              #  max(dp(K-1,i-1),dp(K,N-i))+1
               # )
            ###二分優化，見labuladong
            l,r=1,N
            while(l<=r):
                mid=(r+l)//2
                broken=dp(K-1,mid-1)
                notbroken=dp(K,N-mid)
                if(notbroken>broken):
                    l=mid+1
                    res=min(res,notbroken+1)
                else:
                    r=mid-1
                    res=min(res,broken+1)

            memo[(K,N)]=res

            return res
        return dp(K,N)
           

解法二：非遞歸版動态規劃

修改

dp

數組的定義，确定目前的雞蛋個數和最多允許的扔雞蛋次數(m)，就知道能夠确定

F

的最高樓層數（參考連結2)

dp[k][m] = n
# 目前有 k 個雞蛋，可以嘗試扔 m 次雞蛋
# 這個狀态下，最壞情況下最多能确切測試一棟 n 層的樓

# 比如說 dp[1][7] = 7 表示：
# 現在有 1 個雞蛋，允許你扔 7 次;
# 這個狀态下最多給你 7 層樓，
# 使得你可以确定樓層 F 使得雞蛋恰好摔不碎
# （一層一層線性探查嘛）
           

我們最終要求的其實是扔雞蛋次數

m

，但是這時候

m

在狀态之中而不是

dp

數組的結果，可以這樣處理：

int superEggDrop(int K, int N) {

    int m = 0;
    while (dp[K][m] < N) {
        m++;
        // 狀态轉移...
    }
    return m;
}
           

1、無論你在哪層樓扔雞蛋，雞蛋隻可能摔碎或者沒摔碎，碎了的話就測樓下，沒碎的話就測樓上。

2、無論你上樓還是下樓，總的樓層數 = 樓上的樓層數 + 樓下的樓層數 + 1（目前這層樓）。

根據這個特點，可以寫出下面的狀态轉移方程：

dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1

dp[k][m - 1]

就是樓上的樓層數，因為雞蛋個數

k

不變，也就是雞蛋沒碎，扔雞蛋次數

m

減一；

dp[k - 1][m - 1]

就是樓下的樓層數，因為雞蛋個數

k

減一，也就是雞蛋碎了，同時扔雞蛋次數

m

減一。

優化二維的解法就是利用一維，将dp改成一維，這是因為二維dp更新時每次用到了上方元素和左上方元素，是以更新一維時要從後往前更新，這樣上方和左上方的元素才沒有被更改過。（參考連結3）

下面代碼中被注釋的是二維解法

class Solution {
    public int superEggDrop(int K, int N) {
        //int [][]dp=new int[K+1][N+1];

        int []dp=new int [K+1];

        int ans=0;
        while(dp[K]<N){
            ans++;
            for(int i=K;i>=1;i--)//一維數組反向周遊
                dp[i]=dp[i]+dp[i-1]+1;
        }
        return ans;

        /*int m=0;//二維數組正向周遊
        while(dp[K][m]<N){
            m++;
            for(int k=1;k<=K;k++){
                dp[k][m]=dp[k-1][m-1]+dp[k][m-1]+1;
            }
        }
        return m;
        */

    }
}