1
class Solution:
2
    def superEggDrop(self, e: int, f: int) -> int:
3
        dp = [[-1 for _ in range(e + 1)] for _ in range(f + 1)]
4

5
        def solve(floors, eggs):
6

7
            if eggs == 1:
8
                dp[floors][eggs] = floors
9
                return floors
10

11
            if floors == 0:
12
                dp[floors][eggs] = 0
13
                return 0
14

15
            if dp[floors][eggs] == -1:
16

17
                ans = math.inf
18
                low = 1
19
                high = floors
20
                # Binary Search for the floor where to drop the egg
21
                while low <= high:
22
                    mid = (low + high) // 2
23
                    left = solve(mid - 1, eggs - 1)
24
                    right = solve(floors - mid, eggs)
25
                    tmp = 1 + max(left, right)
26
                    if left < right:
27
                        low = mid + 1
28
                    else:
29
                        high = mid - 1
30
                    ans = min(ans, tmp)
31

32
                dp[floors][eggs] = ans
33

34
            return dp[floors][eggs]
35

36
        return solve(f, e)