Leetcode刷题(14) 高楼扔鸡蛋

具体方法参考labuladong的经典动态规划：高楼扔鸡蛋

动态规划问题

887. 鸡蛋掉落

方法一: 动态规划，线性搜索 (python超时)

class Solution(object): def superEggDrop(self, K, N): """ :type K: int :type N: int :rtype: int """ # 备忘录 mome = dict() def dp(k, n): # base case if k == 1: return n if n == 0: return 0 if (k, n) in mome: return mome[(k, n)] # 选择 res = float('inf') for i in range(1, n + 1): res = min(res, max( dp(k - 1, i - 1), # 蛋碎了, 到下区间的楼层 dp(k, n - i) # 蛋很坚强没有碎, 到上区间的楼层 ) + 1 # 记住扔了一次鸡蛋 +1 ) mome[(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 """ # 备忘录 mome = dict() def dp(k, n): # base case if k == 1: return n if n == 0: return 0 if (k, n) in mome: return mome[(k, n)] # 初始化左右下标 l = 1 r = n res = float('inf') # 闭区间内搜索目标 while(l <= r): # 更新mid mid = l + (r-l) / 2 # 先得到蛋碎和没碎的dp返回值 dansui = dp(k - 1, mid - 1) danmeisui = dp(k, n - mid) # 比较, 取得更大的 if dansui > danmeisui: # 蛋碎 # 向下层楼搜索 r = mid - 1 res = min(dansui + 1, res) else: # 蛋没碎 # 向上层楼搜索 l = mid + 1 res = min(danmeisui + 1, res) mome[(k, n)] = res return res return dp(K, N)