Problem statement

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

Solution

Let us try to solve a bit different problem instead: given T moves and K eggs, denote by f(T, K) the highest floor we can solve problem for. Then we need to find the smallest T, such that f(T, K) >= N. We can write down the following recursion:

f(T, K) = 1 + f(T-1, K-1) + f(T-1, K)

if ball is broken, we can cover f(T-1, K-1) floors, if it is not, we can cover f(T-1, K) floors.

Complexity

Time complexity is O(NK), space complexity as well.

Code

class Solution:
    def superEggDrop(self, K, N):
        dp = [[0] * (K+1) for _ in range(N+1)]
 
        for i in range(1, N+1):
            for j in range(1, K+1):
                dp[i][j] = 1 + dp[i-1][j-1] + dp[i-1][j]
            if dp[i][K] >= N: return i

Remark

Moreover, it can be shown that $f(T, k) = C_T^1 + \dots + C_T^k$ and using this information, problem can be solved in O(K log N), using binary search.