# 887. Super Egg Drop 鸡蛋掉落

@TOC

## # 题目描述

You are 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.

You know 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`

## # 解题方法

``````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

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 = i
if m == 1 and g >= h:
return i

``````

## # 日期

2018 年 11 月 7 日 —— 天冷加衣！