leetcode 887.鸡蛋掉落

class Solution(object):
    def superEggDrop(self, K, N):
        memo = dict()
        def dp(k, n):
            if k == 1: return n
            if n == 0: return 0
            if (k,n) in memo:
                return memo[(k, n)]
            low, high = 1, n
            res = float('INF')
            while low <= high:
                mid = (low+high)//2
                broken = dp(k-1, mid-1)
                not_broken = dp(k, high - mid)
                if broken > not_broken:
                    high = mid- 1
                    res = min(res, broken+1)
                else:
                    low = mid + 1
                    res = min(res, not_broken+1)

            memo[(k,n)] = res
            return res
        return dp(K,N)

class Solution(object):
    def superEggDrop(self, K, N):
        """
        :type K: int
        :type N: int
        :rtype: int
        """
        dp = [[0] * (N+1) for _ in range(K+1)]
        m = 0 
        while dp[K][m] < N:
            m+=1
            for k in range(1, K+1):
                dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1
        
        return m