887. Super Egg Drop

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # time O(K*NlgN) space O(KN)
        # initialize dp[K][N] 
        memo = {}
        def dp(K,N):
            # base case 
            if K == 1:
                return N
            if N == 0:
                return 0
            if (K,N) in memo:
                return memo[(K,N)]
            
            # make choice
            res = float('inf')
            # for i in range(1,N+1):
            #     res = min(res,
            #               max(
            #                   dp(K-1,i-1),
            #                   dp(K,N-i)
            #                 )+1
            #              )
            l,r = 1,N
            while l<=r:
                mid = l + (r-l)//2
                broken = dp(K-1,mid-1)
                un_broken = dp(K,N-mid)
                if broken > un_broken:
                    r = mid -1
                    res = min(res,broken+1)
                else:
                    l = mid + 1
                    res = min(res,un_broken+1)
                
            memo[(K,N)] = res 
            return res
        return dp(K,N)