leetcode887.雞蛋掉落

轉載自labuladong題解

思路

解法一（逾時）：

複雜度

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(K, N) -> int:
            # base case
            if K == 1: return N
            if N == 0: return 0
            # 避免重複計算
            if (K, N) in memo:
                return memo[(K, N)]
            res = float('INF')
            # 窮舉所有可能的選擇
            for i in range(1, N + 1):
                res = min(res, max(dp(K, N - i), dp(K - 1, i - 1)) + 1)
            # 記入備忘錄
            memo[(K, N)] = res
            return res
        
        return dp(K, N)
           

解法二（二分法優化）：

思路

複雜度

def superEggDrop(self, K: int, N: int) -> int:
        
    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)]                         
        res = float('INF')
        # 用二分搜尋代替線性搜尋
        lo, hi = 1, N
        while lo <= hi:
            mid = (lo + hi) // 2
            broken = dp(K - 1, mid - 1) # 碎
            not_broken = dp(K, N - mid) # 沒碎
            # res = min(max(碎，沒碎) + 1)
            if broken > not_broken:
                hi = mid - 1
                res = min(res, broken + 1)
            else:
                lo = mid + 1
                res = min(res, not_broken + 1)

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