887.md

887 Super Egg Drop

Description

link

---

Solution DP TLE

dp[k][n] : steps to use k eggs to detect n floors

Recrusive : dp[k][n] = min(1 + max(dp[k - 1][i - 1], dp[k][n - i])) i = 1...n. (image one egg to detect i floor)

Initial :

• dp[0][i]=0, i=1...N # no egg, no floor can check
• dp[1][i]=i, i=1...N # one egg, check floor from i to 1
• dp[j][1]=1, j=1...K # one floor, only check once

---

Code

Complexity T : O(KN^2) M : O(KN)

class Solution:
    def superEggDrop(self, K, N):
        """
        :type K: int
        :type N: int
        :rtype: int
        """
        # dp[k][n] : steps to use k eggs to detect n floors
        # Recrusive : dp[k][n] = min(1 + max(dp[k - 1][i - 1], dp[k][n - i])) i = 1...n. (image one egg to detect i floor)
        # Initial :
        #   dp[0][i]=0, i=1...N # no egg, no floor can check
        #   dp[1][i]=i, i=1...N # one egg, check floor from i to 1
        #   dp[j][1]=1, j=1...K # one floor, only check once
        
        dp = [[0] * (N + 1) for _ in range(K + 1)]
        
        for i in range(1, N + 1):
            dp[0][i] = 0
            dp[1][i] = i
        for j in range(1, K + 1):
            dp[j][1] = 1
        
        for k in range(2, K + 1):
            for n in range(2, N + 1):
                dp[k][n] = float("inf")
                for i in range(1, n + 1):
                    dp[k][n] = min(dp[k][n], 1 + max(dp[k - 1][i - 1], dp[k][n - i]))
        
        return dp[K][N]

---

Follow UP : DP

dp[M][K] : given K eggs and M moves, what is the maximum number of floor that we can check.

Recrusive :

• dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
• if egg breaks, then we can check dp[m - 1][k - 1] floors.
• if egg doesn't breaks, then we can check dp[m - 1][k] floors.

dp[m][k] is similar to the number of combinations and it increase exponentially to N

The dp equation is:

dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1,
assume, dp[m-1][k-1] = n0, dp[m-1][k] = n1
the first floor to check is n0+1.
if egg breaks, F must be in [1,n0] floors, we can use m-1 moves and k-1 eggs to find out F is which one.
if egg doesn't breaks and F is in [n0+2, n0+n1+1] floors, we can use m-1 moves and k eggs to find out F is which one.
So, with m moves and k eggs, we can find out F in n0+n1+1 floors, whichever F is.

---

Code

Complexity T : O(KN) M : O(KN)

class Solution:
    def superEggDrop(self, K, N):
        """
        :type K: int
        :type N: int
        :rtype: int
        """
        # dp[M][K] : given K eggs and M moves, what is the maximum number of floor that we can check.
        # dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
        # if egg breaks, then we can check dp[m - 1][k - 1] floors.
        # if egg doesn't breaks, then we can check dp[m - 1][k] floors.

        # dp[m][k] is similar to the number of combinations and it increase exponentially to N
        
        dp = [[0] * (K + 1) for _ in range(N + 1)]
        
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
            if dp[m][K] >= N: return m

---

Follow UP O(K) space

delete m demension

---

Code

class Solution:
    def superEggDrop(self, K, N):
        """
        :type K: int
        :type N: int
        :rtype: int
        """
        # dp[M][K] : given K eggs and M moves, what is the maximum number of floor that we can check.
        # dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
        # if egg breaks, then we can check dp[m - 1][k - 1] floors.
        # if egg doesn't breaks, then we can check dp[m - 1][k] floors.

        # dp[m][k] is similar to the number of combinations and it increase exponentially to N
        
        dp = [0] * (K + 1)
        
        for m in range(1, N + 1):
            for k in range(K, 0, -1):
                dp[k] = dp[k] + dp[k - 1] + 1
            if dp[K] >= N: return m