题目地址：https://leetcode.com/problems/super-egg-drop/description/
题目描述
Youare given K eggs, and you have access to a building with N floors from 1 to N.
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
Youknow that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
Example 1:
Input: K = 1, N = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6
Output: 3
Example 3:
Input: K = 3, N = 14
Output: 4
Note:
1、 1<=K<=100；
2、 1<=N<=10000；
题目大意
有一个高度是N层的楼，有K个鸡蛋。存在一个楼层F，使得比F高的楼层上扔下来的鸡蛋都会碎，在F层以及以下的楼层扔下来的鸡蛋都不会碎。每次移动我们可以使用一个鸡蛋从第X层楼上扔下来，目标是找出这个F，问需要最小的移动次数是多少？
解题方法
这个题已经超出了我的能力范围了，不过有个师兄的文章写的超级好，对这个题分析了1万多字，可以在这里看到：【直观算法】Egg Puzzle 鸡蛋难题open in new window。
class Solution:
def superEggDrop(self, K, N):
"""
:type K: int
:type N: int
:rtype: int
"""
h, m = N, K
if h < 1 and m < 1: return 0
t = math.floor( math.log2( h ) ) + 1
if m >= t: return t
else:
g = [ 1 for i in range(m + 1) ]
g[0] = 0
if g[m] >= h: return 1
elif h == 1: return h
else:
for i in range(2, h + 1):
for j in range( m, 1, -1):
g[j] = g[j - 1] + g[j] + 1
if j == m and g[j] >= h:
return i
g[1] = i
if m == 1 and g[1] >= h:
return i
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发