# Super Egg Drop

RecursionDP

## # Solution

See this video in Chinese (opens new window) for perfect explanation on this problem and the previous easier problem Drop Eggs.

Let $i$ be the one of K eggs, and $j$ be one of the N floors.

### # Iterative DP (TLE)

The state transition is:

$dp(i, j) = \min_{1 \le k \le j}\left(\max(dp(i-1, k-1), dp(i, j-k)) \right)$

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][j-k].

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(KN^2)$
space: $O(KN)$

def superEggDrop(self, K, N):
res = [[sys.maxsize for _ in range(N+1)] for _ in range(K+1)]

for i in range(1, K+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, K+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]

1
2
3
4
5
6
7
8
9
10
11
12
13

### # Recursive DP w/ Memoization (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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

### # DP w/ Optimality Criterion (REDO)

def superEggDrop(self, K, 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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

### # 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

1
2
3
4
5
6
7
8