Super Egg Drop

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

This problem is equivalent to Drop Eggs II at Lintcode but harder to pass.

# Solution

See this video for perfect explanation on this problem and the previous easier problem.

# Iterative DP (TLE)

Let i be the one of m eggs and j be one of the n floors. The recurrence relation is:

dp(i,j)=min1kj(max(dp(i1,k1),dp(i,jk)))dp(i, j) = \min_{1 \le k \le j}\left(\max(dp(i-1, k-1), dp(i, j-k)) \right)

# Explanation on Recurrence Relation

If ith egg breaks at kth floor, there are i-1 eggs left and critical floor exists below k, so problem is reduced to res[i-1][k-1].

Else, ith egg doesn't break and critical floor exists btw k and j, so problem is reduced to res[i][k-j].

Note:

  • plus 1 for initial drop
  • max takes into account the worst case
  • min takes the number of drops for the best way to drop ith egg at optimal kth floor

Complexity:

  • time: O(mn2)O(mn^2)
  • space: O(mn)O(mn)
class Solution:
    """
    @param m: the number of eggs
    @param n: the number of floors
    @return: the number of drops in the worst case
    """
    def dropEggs2(self, m, n):
        res = [[sys.maxsize]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            res[i][0] = 0
            res[i][1] = 1
        for j in range(1, n+1):
            res[1][j] = j
        for i in range(2, m+1):
            for j in range(2, n+1):
                for k in range(1, j+1):
                    res[i][j] = min(res[i][j], 1 + max(res[i-1][k-1], res[i][j-k]))
        return res[m][n]

# Recursive DP (TLE)

The recursive DP w/ memoization also TLE.

    def superEggDrop(self, K, N):
        if N == 0 or N == 1:
            return N
        if K == 1:
            return N
        min = sys.maxsize

        # Consider all droppings from 1st
        # floor to kth floor and return
        # the minimum of these values plus 1.
        for x in range(1, N + 1):

            res = 1 + max(self.superEggDrop(K - 1, x - 1),
                      self.superEggDrop(K, N - x))
            if (res < min):
                min = res

        return min

# DP w/ Optimality Criterion (REDO)

class Solution:
    """
    @param m: the number of eggs
    @param n: the number of floors
    @return: the number of drops in the worst case
    """
    def dropEggs2(self, m, n):
        # Right now, dp[i] represents dp(1, i)
        dp = range(N+1)

        for k in range(2, K+1):
            # Now, we will develop dp2[i] = dp(k, i)
            dp2 = [0]
            x = 1
            for n in range(1, N+1):
                # Let's find dp2[n] = dp(k, n)
                # Increase our optimal x while we can make our answer better.
                # Notice max(dp[x-1], dp2[n-x]) > max(dp[x], dp2[n-x-1])
                # is simply max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)).
                while x < n and max(dp[x-1], dp2[n-x]) > max(dp[x], dp2[n-x-1]:
                    x += 1

                # The final answer happens at this x.
                dp2.append(1 + max(dp[x-1], dp2[n-x]))

            dp = dp2

        return dp[-1]

# Math (REDO)

def superEggDrop(self, K, N):
    dp = [[0 for col in range(K + 1)] for row in range(N + 1)]
    m = 0
    while dp[m][K] < N
        m = m + 1
        for i in range(1,K + 1)
            dp[m][i] = dp[m - 1][i - 1] + dp[m - 1][i] + 1
    return m
Last Updated: 9/21/2020, 4:44:16 PM